興味深い解決策は、n より小さいすべての素数を取得することです。

ここでは、n 未満のすべての素数を効率的な方法で生成する方法を見ていきます。この方法ではウィルソンの定理を使用します。彼の定理によれば、数値 k が素数の場合、((k - 1)! 1) mod k は 0 になります。このアイデアを得るアルゴリズムを見てみましょう。

このアイデアは、大きな整数をサポートしていないため、C や C のような言語では直接機能しません。階乗は大きな数を生成します。

Algorithm

genAllPrime(n)

Begin
   fact := 1
   for i in range 2 to n-1, do
      fact := fact * (i - 1)
      if (fact + 1) mod i is 0, then
         print i
      end if
   done
End

Example

の中国語訳は次のとおりです:

Example

#include <iostream>
using namespace std;
void genAllPrimes(int n){
   int fact = 1;
   for(int i=2;i<n;i++){
      fact = fact * (i - 1);
      if ((fact + 1) % i == 0){
         cout<< i << " ";
      }
   }
}
int main() {
   int n = 10;
   genAllPrimes(n);
}

Output

2 3 5 7

以上が興味深い解決策は、n より小さいすべての素数を取得することです。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。