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

概念

对于给定的正数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
猜你喜欢