素数筛

筛法求素数

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

埃氏筛

void get_prime(long long n)
{
    tot = 0;
    memset(is, 1, sizeof(is));///bool类型数组全部初始化为1（默认全为质数）
    is[0] = is[1] = 0;///0、1不是质数，单列
    for(int i = 2; i <= n; ++i)///遍历数组
    {
        if(is[i])///若此数未被标为0，则其未被前面质数筛掉，属于质数，用它去筛后面的数
        {
            pri[++tot] = i;///（1）将此数存于质数数组            pri[0]里没存数字
            for(int j = i + i; j <= n; j += i)///（2）从其2倍开始筛
            {
                is[j] = 0;
            }
        }
    }
}

线性筛

每个合数仅被它的最小质因子筛过，且为一次

void prime(int n)
{
    tot = 0;
    memset(vis, 1, sizeof(vis));
    vis[0] = vis[1] = false;
    for (int i = 2; i <= n; i++)
    {
        if (vis[i])
            p[++tot] = i;
        for (int j = 1; j <= tot && p[j] * i <= n; j++)
        {
            vis[p[j]*i] = false;                          ///合数被他的最小质因子筛掉
            if (i % p[j] == 0)                            ///"只"
                break;
        }
    }
}

关于if(i % p[j] == 0)

其功能：保证每个数只被它最小的因子筛掉

其机理:

证明（反证）：

假设 i = k * a（k 为常数、a为较小、较靠前的质数）

如果没有上面那句代码 ，ka % a == 0 了还去找下一个素数（a + x）去筛

首先筛掉 (a + x) k a 这个数字

我们发现那个数字的所有因子中，a 是比 （a + x）更小的

那就违背线性筛概念了，反证得这句代码很重要

//I'm not sure if we need this, but too scared to delete.