埃氏素数筛 On

const int N = 1e+6 + 7;  
bool prime[N];  
int rec[N], cnt;  
void init_prime_table(int n)  
{  
    cnt = 0;  
    memset(prime, true, sizeof(prime));  
    prime[0] = prime[1] = false;  
    for (int i = 2; i <= n; ++i)  
    {  
        if (prime[i])  
            rec[cnt++] = i;  
        //此处边界判断为rec[j] <= n / i,如果写成i * rec[j] <= n,需要确保i * rec[j]不会溢出int  
        for (int j = 0; j < cnt && rec[j] <= n / i; ++j)  
        {  
            prime[i * rec[j]] = false;  
            if (i % rec[j] == 0)  
                break;  
        }  
    }  
}