埃氏筛法的的核心是： 素数的倍数都不是素数。

那我们执行这样一个策略， 我们可以确定的是 2 是最小的素数， 创建一个表并将除了 0 1 外的所有数标记为素数，我们将筛选范围内的 2 的倍数全部标记为合数(非素数)，然后取出表中最小的素数，执行相同的策略(讲素数的倍数标记为非素数)。下图可以完美的演示这样一个算法

 

埃氏筛的复杂度仅有O（nloglogn），算是比较快的了。当数据量不是太大的时候，可以把它的复杂度看作是线性的。

const int max_num = 10000 + 10;bool is_prime[max_num];void prime_table(int maxn){    memset(is_prime, 1, sizeof(is_prime));    is_prime[0] = is_prime[1] = false;    for(int i = 2; i <= maxn; i++)    {        if(is_prime[i])        {            for(int j = 2 * i; j <= maxn; j += i)                is_prime[j] = false;        }    }}