資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告