一個有趣的解決方案是取得所有小於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

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

輸出

2 3 5 7

以上是一個有趣的解決方案是取得所有小於n的質數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！