算法

朴素筛法

算法思想

前言
Eratosthenes 筛法利用的原理是 任意整数 x 的倍数 2x，3x，… 等都不是质数 。
但是即便如此也会有重复标记的现象，例如12既会被2又会被3标记，在标记2的倍数时，12=6∗2
，在标记3的倍数时，12=4∗3 ，根本原因是没有找到唯一产生12的方式。

线性筛法
假设 i 是合数 t 的最大因数，t显然可能不唯一（例如 30 和 45 最大因数都是 15）。但是仔细想一想，必然有
t = i * p(p为小于 i 的质数) 。
p为什么比 i 小？因为 i 是 t 的最大因数。
为什么 p 一定是质数？因为如果 p 是合数，那么 i 就一定不是 t 的最大因数，因为 p可以再拆成若干素数相乘，这些素数再与 i 相乘会使因数更大。
既然如此，我们只需要把所有小于 i 的质数 p 都挨个乘一次好了。可是，真相真的是这样的嘛？
其实不是的，一不小心就忘记了最初的条件。我们要满足 i 是 t 的最大因数。如果 p 大于 i 的最小质因数，那 i 还是 t 的最大因数嘛？显然不是，任何一个合数都能唯一分解为有限个质数的乘积，除去这其中最小的质因数，其他的都乘起来就是最大因数 i 。所以我们不能让 p 大于 i 的最小质因数。

算法核心代码

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

//primes数组用来存放质数
int primes[N], cnt;
//st[i], i为质数则为false否则为true
bool st[N];

void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        //假设primes[0]为n最小的质因子,i为最大的因数，
        //易知若primes[i]中i>0,则会进入循环后产生多余的标记。
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            //标记;primes[j]一定是primes[j]*i的最小质因子
            st[primes[j]*i] = true;
            //表明primes[j]一定是i的最小质因子,没有必要再遍历,primes要小于等于i的最小质因子
            //这样能保证每个数遍历一遍,而没有重复
            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}