素数筛选算法

2016-05-19 / ACM-ICPC Number Theory

一个快速的筛选从0到一个数字之前所有素数的方法,思路比较简单:先把所有数字都标记为素数,然后从2开始一直到n,当这个数字i的标记为素数,就把 i * i, i * (i+1), i * (i+2), … , 全部标记为非素数即可。

#include <iostream>
using namespace std;

// max number
#define MAXN 1024

int main () {
    bool is_prime[MAXN+1];
    for (int i = 0; i <= MAXN; i++){
        is_prime[i] = true;
    }
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; i <= MAXN; i++){
        if (is_prime[i]){
            for (int j = i * i; j <= MAXN; j += i){
                is_prime[j] = false;
            }
        }
    }
    // done for judge all number wether it is a prime.
    // ----------------------------------------------
    // output all prime number between 0-MAXN
    for (int i = 0; i <= MAXN; i++){
        if(is_prime[i]){
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}