C ++中的原始性测试

在这个问题中，给我们一个数字N，我们的任务是检查它是否是质数。

素数测试是用于检查给定数字是否为素数的算法。

质数是一个只能由其自身除的数。示例：2、3、5、7。

让我们举一个例子来了解我们的问题，

Input: 11
Output: Yes

有多种方法可以检查数字的素数测试。

一种检查素数的简单方法是通过将数除以小于N的所有数字来进行检查。如果有任何数除以N，则它不是质数。

检查所有i = 2-n-1。如果n / i == 0，则它不是质数。

通过在算法中进行这些小的更改，可以使此方法更有效。

首先，我们应该检查直到√n而不是n的值。这将节省很多循环值。√n包括n的所有可能因子的值。

其他变化可能是检查被2和3除。然后检查从5到√n的循环值。

程序展示了该算法的实现

示例

#include <iostream>
using namespace std;
bool isPrimeNumber(int n){
   if (n <= 1)
      return false;
   if (n <= 3)
   return true;
   if (n % 2 == 0 || n % 3 == 0)
      return false;
   for (int i = 5; i * i <= n; i = i + 6)
   if (n % i == 0 || n % (i + 2) == 0)
   return false;
   return true;
}
int main() {
   int n = 341;
   if (isPrimeNumber(n))
      cout<<n<<" 是素数。";
   else
      cout<<n<<" 不是素数。";
   return 0;
}

输出结果

341 不是素数。

从数字的素性进行检验的另一种更有效的方法是使用基于费马小定理的费马方法。

费马小定理 对于素数N，x的每个值都属于(1,n-1)。以下是正确的，

a n-1 ≡ 1 (mod n)
or
a n-1 % n = 1

演示该定理实施的程序，

示例

#include <iostream>
#include <math.h>
using namespace std;
int power(int a, unsigned int n, int p) {
   int res = 1;
   a = a % p;
   while (n > 0){
      if (n & 1)
      res = (res*a) % p;
      n = n/2;
      a = (a*a) % p;
   }
   return res;
}
int gcd(int a, int b) {
   if(a < b)
      return gcd(b, a);
   else if(a%b == 0)
      return b;
   else return gcd(b, a%b);
}
bool isPrime(unsigned int n, int k) {
   if (n <= 1 || n == 4) return false;
   if (n <= 3) return true;
   while (k>0){
      int a = 2 + rand()%(n-4);
      if (gcd(n, a) != 1)
         return false;
      if (power(a, n-1, n) != 1)
         return false;
      k--;
   }
   return true;
}
int main() {
   int k = 3, n = 23;
   if(isPrime(n, k)){
      cout<<n<<" is a prime number";
   }
   else
      cout<<n<<" is not a prime number";
   return 0;
}

输出结果

23 is a prime number