এই সমস্যায়, আমাদের একটি সংখ্যা দেওয়া হয়েছে এবং আমাদের কাজ হল এটি একটি মৌলিক সংখ্যা কিনা তা পরীক্ষা করা।
প্রাথমিক পরীক্ষা s অ্যালগরিদম যা প্রদত্ত সংখ্যাটি মৌলিক কিনা তা পরীক্ষা করতে ব্যবহৃত হয়।
মৌলিক সংখ্যা হল এমন একটি সংখ্যা যা শুধুমাত্র নিজের দ্বারা ভাগ করা যায়। উদাহরণ:2, 3, 5, 7.
আমাদের সমস্যা বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input: 11 Output: Yes
একটি সংখ্যার প্রাথমিক পরীক্ষা পরীক্ষা করার জন্য একাধিক পদ্ধতি রয়েছে।
প্রাইমালিটি চেক করার একটি সহজ পদ্ধতি হল N এর চেয়ে কম সব সংখ্যা দিয়ে সংখ্যার বিভাজন চেক করা। যদি কোন সংখ্যা N কে ভাগ করে, তাহলে সেটা মৌলিক সংখ্যা নয়।
সমস্ত i =2 - n-1 জন্য পরীক্ষা করুন। n/i ==0 হলে, এটি মৌলিক সংখ্যা নয়।
অ্যালগরিদমে এই ছোট পরিবর্তনগুলি করে এই পদ্ধতিটিকে আরও কার্যকর করা যেতে পারে।
প্রথমে, আমাদের n এর পরিবর্তে √n পর্যন্ত মান পরীক্ষা করা উচিত। এটি অনেক লুপ মান সংরক্ষণ করবে। √n-এর মধ্যে n-এর সম্ভাব্য সকল গুণনীয়কের মান অন্তর্ভুক্ত।
অন্যান্য পরিবর্তন হতে পারে 2 এবং 3 দ্বারা বিভাজন পরীক্ষা করা। তারপর 5 থেকে √n থেকে লুপের মান পরীক্ষা করা।
এই অ্যালগরিদমের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম
উদাহরণ
#include <iostream>
using namespace std;
bool isPrimeNumber(int n){
if (n <= 1)
return false;
if (n <= 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
int main() {
int n = 341;
if (isPrimeNumber(n))
cout<<n<<" is prime Number.";
else
cout<<n<<" is not prime Number.";
return 0;
} আউটপুট
341 is not prime Number.
একটি সংখ্যার আদিমতা যাচাই করার জন্য অন্য আরও কার্যকর পদ্ধতি হল Fermat's পদ্ধতি ব্যবহার করা যা ফার্মাটের লিটল থিওরেমের উপর ভিত্তি করে।
ফার্মাটের ছোট্ট উপপাদ্য একটি মৌলিক সংখ্যা N এর জন্য, x এর প্রতিটি মান (1, n-1) এর অন্তর্গত। নীচের সত্য,
a n-1 ≡ 1 (mod n) or a n-1 % n = 1
এই উপপাদ্যের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
#include <math.h>
using namespace std;
int power(int a, unsigned int n, int p) {
int res = 1;
a = a % p;
while (n > 0){
if (n & 1)
res = (res*a) % p;
n = n/2;
a = (a*a) % p;
}
return res;
}
int gcd(int a, int b) {
if(a < b)
return gcd(b, a);
else if(a%b == 0)
return b;
else return gcd(b, a%b);
}
bool isPrime(unsigned int n, int k) {
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
while (k>0){
int a = 2 + rand()%(n-4);
if (gcd(n, a) != 1)
return false;
if (power(a, n-1, n) != 1)
return false;
k--;
}
return true;
}
int main() {
int k = 3, n = 23;
if(isPrime(n, k)){
cout<<n<<" is a prime number";
}
else
cout<<n<<" is not a prime number";
return 0;
} আউটপুট
23 is a prime number
