筛法求素数的基本思想：

把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。

一般的素数筛选法：

void Is_prime(int n)
{
    prime[0] = prime[1] = false;

    for(int i = 2;i < n; i++)

        prime[i] = true;

    for(int i = 2;i < n;i ++)
    {
        if(prime[i])
        {
            for(int j = i*i; j <= n;j+=i)  // j = i * 2 也可以,但会发现 j = i * i 更好
                prime[j] = false;
        }
    }

}

但是还是会发现有不如意的地方，会有重复运算出现，比如 6=2*3的时候，在素数2的时候筛选了一遍，在素数为3时又筛选了一遍。那么如何减少重复运算呢？

优化的素数筛选法：

bool prime[Max_n];
int sus[Max_n];

void Is_prime(int n)
{
    int cnt = 0;

    prime[0] = prime[1] = false;

    for(int i = 2;i < n; i++)
        prime[i] = true;

    for(int i = 2;i < n;i ++)
    {
        if(prime[i])
            sus[cnt++] = i;  //保存素数i

        for(int j = 0;j < cnt && sus[j]*i <= n;j++)
        {
            prime[sus[j]*i] = false;
            if(i%sus[j] == 0)break;
        }
    }
}