对于给定的正数n,任务是验证n是否为原始质数。如果n是原始质数,我们必须打印“是”,否则打印“否”。
素数素数-对于数学,素数素数定义为形式为pN#+ 1或pN#– 1的素数,其中pN#是pN的素数,使得前N个素数为乘积。
输入-n = 7
输出-是
7是形式为N = 2的pN + 1形式的本原素,本原素是2 * 3 = 6和6 + 1 = 7。
输入-n = 29
输出-是
29是pN-1形式的Primorial素数,N = 3,Primorial是2 * 3 * 5 = 30且30-1 = 29。
在下面的代码中,前几个原始质数被显示-2,3,5,5,7,29,31,211,2309,2311,30029
我们必须通过应用Eratosthenes筛子来生成范围内的所有素数。
验证N是否为质数,如果N不是质数,则打印否
否则,从第一个质数(即2)开始乘以下一个质数,并继续验证乘积+ 1 = N或乘积– 1 = N
已经看到,如果乘积+ 1 = N或乘积-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){ //如果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; //检查n是否为Primorial Prime- if (isPrimorialPrime1(n)) cout << "YES\n"; else cout << "NO\n"; return 0; }
输出结果
YES