
在这里我们将看到如何以高效的方式生成小于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 fact="fact" if i="=" int main n="10;"><h2>输出</h2>
<pre class="brush:php;toolbar:false;">2 3 5 7











