C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

フェルマーの素数性テストを実行するC++プログラム


フェルマーの素数性テストは、与えられた数が素数であるかどうかをチェックするために実行されます。これがこのアルゴリズムのC++コードです。

アルゴリズム

Begin
   modulo(base, e, mod)
   a = 1
   b = base
   while (e > 0)
      if (e mod 2 == 1)
         a = (a * b) % mod
         b = (b * b) % mod
         e = e / 2
      return a % mod
End

Begin
   Fermat(ll m, int iterations)
   if (m == 1)
      return false
   done
   for (int i = 0; i < iterations; i++)
      ll x = rand() mod (m - 1) + 1
      if (modulo(x, m - 1, m) != 1)
         return false
      done
   return true
End

サンプルコード

#include <cstring>
#include <iostream>
#include <cstdlib>
#define ll long long
using namespace std;
ll modulo(ll base, ll e, ll mod) {
   ll a = 1;
   ll b = base;
   while (e > 0) {
      if (e % 2 == 1)
         a = (a * b) % mod;
         b = (b * b) % mod;
         e = e / 2;
   }
   return a % mod;
}
bool Fermat(ll m, int iterations) {
   if (m == 1) {
      return false;
   }
   for (int i = 0; i < iterations; i++) {
      ll x = rand() % (m - 1) + 1;
      if (modulo(x, m - 1, m) != 1) {
         return false;
      }
   }
   return true;
}
int main() {
   int iteration = 70;
   ll num;
   cout<<"Enter integer to test primality: ";
   cin>>num;
   if (Fermat(num, iteration))
      cout<<num<<" is prime"<<endl;
   else
      cout<<num<<" is not prime"<<endl;
   return 0;
}

出力

Enter integer to test primality: 13 is prime

  1. 複素数の乗算を実行するC++プログラム

    複素数は、a + biとして表される数です。ここで、iは虚数、aとbは実数です。複素数の例は次のとおりです- 2+3i 5+9i 4+2i 複素数の乗算を実行するプログラムは次のとおりです- 例 #include<iostream> using namespace std; int main(){    int x1, y1, x2, y2, x3, y3;    cout<<"Enter the first complex number : "<<endl;    cin&g

  2. 行列乗算を実行するC++プログラム

    行列は、行と列の形式で配置された長方形の数値配列です。 マトリックスの例は次のとおりです。 以下に示すように、3*2マトリックスには3行2列があります- 8 1 4 9 5 6 行列の乗算を実行するプログラムは次のとおりです。 例 #include<iostream> using namespace std; int main() {    int product[10][10], r1=3, c1=3, r2=3, c2=3, i, j, k;    int a[3][3] = { {2, 4, 1} , {2, 3, 9} , {3