筛法描述:
把 2 到 n 中所有的数列出来， 然后从 2 开始， 先划掉 n 内所有 2 的倍数， 然后每次从下一个剩下的数（必然是素数）开始，划掉其 n 内的所有倍数。最后剩下的数，就都是素数了。
思路：
- 设置一个标志数组 is_prime, is_prime[i] 的值是 1 就表示 i 是素数，开始数组元素值全部为 1
- 划掉 k 的倍数， 就是把 is_prime[2k], is_prime[3k] …… 标记为 0
- 最后检查 is_prime 数组，如果is_prime[i] 值为 1 那么 i 就是素数
实现:
// 筛法求素数
#include <iostream>
#include <cstdio>
using namespace std;
const int max_size = 1000;
// 大数组定义在外面
char is_prime[max_size+1]; // 最终如果 is_prime 为 1，则表示 i 是素数
int main(void)
{
int i, j;
for (i=2; i<max_size+1; i++){ // 开始假设所有数都是素数
is_prime[i] = 1;
}
for(i=2; i<max_size+1; i++){ // 每次将一个素数所有的倍数标记为非素数
if (is_prime[i] == 1){ // 只标记素数的倍数
for (j=2*i; j<max_size+1; j+=i){
is_prime[j] = 0; // 将素数 i 的倍数标记为非素数
}
}
}
for (i=2; i<max_size+1; i++){
if (is_prime[i] == 1){
cout << i << endl;
}
}
return 0;
}
筛法是一种一空间换取时间的方法。
