在C ++中检查数字是否为Primorial Prime

Z时代
2024-01-10
分类：综合

概念

对于给定的正数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;
}