C++での素数性テスト

この問題では、数Nが与えられ、それが素数であるかどうかを確認することがタスクです。

素数性テスト ■指定された数が素数であるかどうかをチェックするために使用されるアルゴリズム。

素数は、それ自体でのみ除算できる数です。例：2、3、5、7。

私たちの問題を理解するために例を見てみましょう

Input: 11
Output: Yes

数の素数性テストをチェックする方法は複数あります。

素数性をチェックする簡単な方法の1つは、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<<" is prime Number.";
   else
      cout<<n<<" is not prime Number.";
   return 0;
}

出力

341 is not prime Number.

数の素数性からチェックする他のより効果的な方法は、フェルマーの方法を使用することです。 これはフェルマーの小定理に基づいています。

フェルマーの小定理 素数Nの場合、（1、n-1）に属するxのすべての値。以下は真実です

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