筛法求素数
程序员文章站
2024-03-15 12:57:47
...
筛法描述:
把 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;
}
筛法是一种一空间换取时间的方法。
上一篇: 求100以内的质数