इस समस्या में, हमें एक संख्या N दी गई है और हमें जांचना है कि यह अभाज्य संख्या (prime number) है या नहीं।
प्राइमैलिटी टेस्ट वह एल्गोरिदम है जिसका उपयोग यह जांचने के लिए किया जाता है कि दी गई संख्या अभाज्य है या नहीं।
अभाज्य संख्या वह संख्या है जो केवल 1 और स्वयं से विभाज्य होती है। उदाहरण: 2, 3, 5, 7।
उदाहरण
Input: 11 Output: Yes
किसी संख्या की प्राइमैलिटी जांचने के कई तरीके हैं।
विधि 1: सरल विधि (O(N))
सभी संख्याओं i = 2 से N-1 तक जांचें कि क्या N, i से विभाज्य है। यदि कोई संख्या विभाजित करती है, तो N अभाज्य नहीं है।
विधि 2: अनुकूलित विधि (O(√N))
हम केवल √N तक जांच कर सकते हैं क्योंकि यदि N का कोई गुणनखंड √N से बड़ा है, तो उसका जोड़ीदार गुणनखंड √N से छोटा होगा।
अतिरिक्त अनुकूलन: 2 और 3 से विभाज्यता जांचें, फिर 5 से √N तक 6 के अंतराल पर (i और i+2) जांचें।
C++ कार्यान्वयन (ट्रायल डिवीजन)
#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 += 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.
विधि 3: फर्मेट की विधि (संभाव्य परीक्षण)
फर्मेट का छोटा प्रमेय: एक अभाज्य संख्या N के लिए, प्रत्येक x ∈ (1, N-1) के लिए:
a^(N-1) ≡ 1 (mod N) या a^(N-1) % N = 1
C++ कार्यान्वयन (फर्मेट टेस्ट)
#include <iostream>
#include <cmath>
#include <cstdlib>
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
