筛选法找素数模板 Anti

const int MAX = 1000010;
bool prime[MAX];
//这是最朴素的筛选法，缺陷是会重复筛同一个数
void isPrime()
{
    memset(prime, 1, sizeof(prime));
    prime[0] = prime[1] = 0;
    for(int i = 4; i <= MAX; i += 2)
        prime[i] = 0;
    for(int i = 3; i <= sqrt(MAX); i++)
    {
        if(prime[i])
        {
            for(int j = i+i; j <= MAX; j += i)
                prime[j] = 0;
        }
    }
}


//这是改进后的算法，避免重复筛同一个数，经测试效率提高很多
void isPrime()
{
    memset(prime, 1, sizeof(prime));
    prime[0] = prime[1] = 0;
    for(int i = 4; i <= MAX; i += 2)
        prime[i] = 0;
    for(int i = 3; i <= sqrt(MAX); i++)
    {
        if(prime[i])
        {
            for(int j = i*i; j <= MAX; j += i+i)
                prime[j] = 0;
        }
    }
}