在这里我们将看到如何以高效的方式生成小于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