獲取小於 n 的所有質數的有趣解決方案？

在此，我們將瞭解如何高效生成小於 n 的所有質數。採用此方法我們將會使用威爾遜定理。根據他的定理，如果一個數字 k 是質數，則 ((k - 1)! + 1) mod k 將是 0。下面我們將看到該演算法以瞭解這一思想。

此思路無法直接在語言中使用 C 或 C++，因為它們不支援大整數。階乘會生成大數字。

演算法

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

示例

#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);
}

輸出

2 3 5 7

Arnab Chakraborty

更新於： 02-Jul-2020

101 次瀏覽

開啟你的 職業 生涯

透過完成課程獲得認證

開始