数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++ 判断一个数是否为素数阶乘素数
概念
对于给定的正数 n，任务是验证 n 是否为素数阶乘素数。如果 n 是素数阶乘素数，则打印“YES”，否则打印“NO”。
素数阶乘素数 - 在数学中，素数阶乘素数定义为形如 pN# + 1 或 pN# – 1 的素数，其中 pN# 是 pN 的素数阶乘，即前 N 个素数的乘积。
输入 - n = 7
输出 - YES
7 是素数阶乘素数，形式为 pN + 1，其中 N=2，素数阶乘为 2*3 = 6，而 6+1 =7。
输入 - n = 29
输出 - YES
29 是素数阶乘素数，形式为 pN - 1，其中 N=3，素数阶乘为 2*3*5 = 30，而 30-1 = 29。
以下是前几个素数阶乘素数：2, 3, 5, 7, 29, 31, 211, 2309, 2311, 30029
方法
我们必须通过应用埃拉托色尼筛法来生成该范围内的所有素数。
验证 N 是否为素数，如果 N 不是素数，则打印 No
否则，从第一个素数（即 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){
// 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
更新于：2020年7月23日
300 次浏览
广告