কনসেপ্ট
দেওয়া ধনাত্মক সংখ্যা n সাপেক্ষে, n প্রাইমোরিয়াল প্রাইম কিনা তা যাচাই করুন। প্রাইমোরিয়াল প্রাইম হলে 'YES' প্রিন্ট করুন অন্যথায় 'NO'।
প্রাইমোরিয়াল প্রাইম − গাণিতিকভাবে, প্রাইমোরিয়াল প্রাইম হল এমন একটি প্রাইম সংখ্যা যা pN# + 1 বা pN# - 1 রূপে প্রকাশ করা যায়, যেখানে pN# হল প্রথম Nটি প্রাইম সংখ্যার গুণফল (প্রাইমোরিয়াল)।
ইনপুট − n = 7
আউটপুট − YES
৭ হল N=2-এর জন্য pN + 1 রূপে প্রাইমোরিয়াল প্রাইম, প্রাইমোরিয়াল = 2*3 = 6 এবং 6+1 = ৭।
ইনপুট − n = 29
আউটপুট − YES
২৯ হল N=3-এর জন্য pN - 1 রূপে প্রাইমোরিয়াল প্রাইম, প্রাইমোরিয়াল = 2*3*5 = 30 এবং 30-1 = ২৯।
প্রথম প্রাইমোরিয়াল প্রাইমগুলো: ২, ৩, ৫, ৭, ২৯, ৩১, ২১১, ২৩০৯, ২৩১১, ৩০০২৯
পদ্ধতি
- Sieve of Eratosthenes দিয়ে সব প্রাইম সংখ্যা জেনারেট করুন।
- N প্রাইম কিনা যাচাই করুন, না হলে No প্রিন্ট করুন।
- অন্যথায়, প্রথম প্রাইম (২) থেকে গুণফল বের করুন এবং চেক করুন product+1=N বা product-1=N কিনা।
- যদি যেকোনো একটিই সত্য হয়, N প্রাইমোরিয়াল প্রাইম।
উদাহরণ
// 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
