अवधारणा
दिए गए धनात्मक संख्या n के संबंध में, यह सत्यापित करना है कि n एक प्राइमोरियल अभाज्य संख्या है या नहीं। यदि n प्राइमोरियल अभाज्य है तो 'YES' प्रिंट करें अन्यथा 'NO'।
प्राइमोरियल अभाज्य: गणित में, एक प्राइमोरियल अभाज्य संख्या pN# + 1 या pN# - 1 के रूप में एक अभाज्य संख्या है, जहां pN# पहले N अभाज्य संख्याओं का गुणनफल है।
उदाहरण
इनपुट - n = 7
आउटपुट - YES
7, N=2 के लिए pN + 1 रूप में प्राइमोरियल अभाज्य है, प्राइमोरियल 2*3 = 6 और 6+1 = 7।
इनपुट - n = 29
आउटपुट - YES
29, N=3 के लिए pN - 1 रूप में प्राइमोरियल अभाज्य है, प्राइमोरियल 2*3*5 = 30 और 30-1 = 29।
पहली कुछ प्राइमोरियल अभाज्य संख्याएं: 2, 3, 5, 7, 29, 31, 211, 2309, 2311, 30029
दृष्टिकोण
- एराटोस्थनीज की छलनी का उपयोग करके सभी अभाज्य संख्याएं उत्पन्न करें।
- जांचें कि N अभाज्य है या नहीं, यदि नहीं तो NO प्रिंट करें।
- पहले अभाज्य (2) से शुरू करके अगली अभाज्य संख्याओं को गुणा करते रहें और जांचें कि गुणनफल + 1 = N या गुणनफल - 1 = N है या नहीं।
- यदि कोई भी शर्त पूरी होती है, तो N एक प्राइमोरियल अभाज्य है।
C++ कार्यान्वयन
// CPP program to check Primorial Prime
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000
vector<int> arr1;
bool prime1[MAX];
void SieveOfEratosthenes1(){
memset(prime1, true, sizeof(prime1));
for (int p = 2; p * p < MAX; p++) {
if (prime1[p] == true) {
for (int i = p * 2; i < MAX; i += p)
prime1[i] = false;
}
}
for (int p = 2; p < MAX; p++)
if (prime1[p])
arr1.push_back(p);
}
bool isPrimorialPrime1(long n){
if (!prime1[n])
return false;
long long product1 = 1;
int i = 0;
while (product1 < n) {
product1 = product1 * arr1[i];
if (product1 + 1 == n || product1 - 1 == n)
return true;
i++;
}
return false;
}
int main(){
SieveOfEratosthenes1();
long n = 29;
if (isPrimorialPrime1(n))
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
आउटपुट
YES