一个有趣的解决方案，使所有素数都小于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