इस समस्या में, हमें एक नंबर N दिया जाता है और हमारा काम यह जांचना है कि यह एक अभाज्य संख्या है या नहीं।
प्राथमिकता परीक्षण 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 की विधि का उपयोग करके किसी संख्या की प्रारंभिकता की जांच करने के लिए अन्य अधिक प्रभावी तरीका है जो फ़र्मेट के छोटे प्रमेय पर आधारित है।
फर्मेट की छोटी प्रमेय एक अभाज्य संख्या 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