개념
주어진 양수 n과 관련하여 작업은 n이 원시 소수인지 여부를 확인하는 것입니다. n이 원시 소수이면 'YES'를 인쇄해야 하고 그렇지 않으면 'NO.
를 인쇄해야 합니다.원시 소수 - 수학과 관련하여 원시 소수는 pN# + 1 또는 pN# – 1 형식의 소수로 정의됩니다. 여기서 pN#은 처음 N 소수의 곱이 되는 pN의 원시입니다.
입력 - n =7
출력 − 예
7은 N=2에 대해 pN + 1 형식의 원시 소수이고, 원시는 2*3 =6 및 6+1 =7입니다.
입력 - n =29
출력 − 예
29는 N=3에 대해 pN - 1 형식의 원시 소수이고, 원시는 2*3*5 =30 및 30-1 =29입니다.
다음에서 처음 몇 개의 원시 소수가 표시됩니다. 2, 3, 5, 7, 29, 31, 211, 2309, 2311, 30029
접근
-
에라토스테네스의 체를 적용하여 범위 내의 모든 소수를 생성해야 합니다.
-
N이 소수인지 확인하고 N이 소수가 아니면 아니오를 인쇄하십시오.
-
그렇지 않으면 첫 번째 소수(즉, 2)에서 시작하여 다음 소수를 곱하기 시작하고 곱 + 1 =N 또는 곱 – 1 =N인지 여부를 계속 확인합니다.
-
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 n is not prime Number
// return flase
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;
}
// Driver code
int main(){
SieveOfEratosthenes1();
long n = 29;
// Check if n is Primorial Prime
if (isPrimorialPrime1(n))
cout << "YES\n";
else
cout << "NO\n";
return 0;
} 출력
YES