筛法求素数

筛法描述:

把 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;
}

筛法是一种一空间换取时间的方法。