868. 筛质数

题目：

给定一个正整数 n，请你求出 1∼n 中质数的个数。

输入格式
共一行，包含整数 n。

输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。

数据范围
1≤n≤106
输入样例：
8
输出样例：
4

1、朴素筛法O(nlogn)：

/** 朴素筛法：从2开始，到N。如果当前元素为p，则把2~p-1中每个元素的倍数删除，留下的一定是质数，因为2~p-1中不存在p的因子 **/
#include <iostream>

using namespace std;

const int N = 1000010;
int primes[N];//保存质数
bool s[N];//标记对应下标的数字是是否已经被删除
int cnt = 0;//标记质数的个数

void getPrime(int n)
{
    
    for(int i = 2; i <= n; i++)
    {
    
        if(!s[i])//从2开始，如果数字i没有被删除，则记录到质数数组中
            primes[cnt++] = i;
        for(int j = i+i; j <= n; j+=i)//遍历n前的数字，删除i的倍数
            s[j] = true;
    }
}
int main()
{
    
    int n;
    cin>>n;
    getPrime(n);
    cout<<cnt<<endl;
    return 0;
}

2、埃氏筛法(nloglogn)：

/** 埃氏筛法：从2开始，到N。如果当前元素为p，则把2~p-1中每个元素的倍数删除，留下的一定是质数，因为2~p-1中不存在p的因子 **/

#include <iostream>

using namespace std;

const int N = 1000010;
int primes[N];
int cnt;
bool s[N];

void getPrimes(int n)
{
    
    for(int i = 2; i <= n; i++)//从2开始遍历，筛选2~n直接的质数
    {
    
        if(!s[i])//如果数字i没有被删除，则说明i是质数
        {
    
            primes[cnt++]  = i;//将质数保存到质数数组中
            for(int j = i+i; j <=n; j+=i)//删除质数i的倍数，合数一定可以被分解成质数
                s[j] = true;//标记合数j被删除
        }
    }
}

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

3、线性筛法O(n)：

/** 线性筛法，原理是1~n中的数，在筛选过程中，一个数一定是被其最小质因子筛掉的 1、i从2枚举到指定的数n 2、如果数字i在此之前没有被筛掉，那么i一定是质数 3、j从0开始枚举已经存在的质数，把合数primes[j]*i筛掉，直到枚举到的primes[j]是i的最小质因子，就退出循环 4、循环的时候，s[ primes[j]*i ]中的primes[j]*i的最小质因子一定是primes[j] 1.i% pj == 0, pj定为i最小质因子，pj也一定为pj*i最小质因子 2.i% pj != 0, pj定小于i的所有质因子，所以pj也一定为pj*i最小质因子 5、一个合数一定会被筛掉 对于一个合数x，假设x的最小质因子是pj，那么当i枚举到x之前，一定会枚举到x/pj时，此时s[ primes[j]* i ]==s[ primes[j]* (x/pj) ]==s[ x ] = true就会筛掉x **/


#include <iostream>

using namespace std;

const int N = 1000010;
int primes[N];
bool s[N];
int cnt;

void getPrimes(int n)
{
    
    for(int i = 2; i <= n; i++)//从2开始遍历到指定的n，筛选出2~n的质数
    {
    
        if(!s[i])primes[cnt++] = i;//如果i没有被筛掉，则为质数
        for(int j = 0; primes[j] <= n / i; j++)//j从0开始，遍历已经有的质数 primes[j] <= n/i是控制筛选小于n的合数primes[j]*i即可
        {
    
            s[ primes[j]*i ] = true;//用最小质因子primes[j]去筛掉合数primes[j]*i
            if(i % primes[j] == 0)break;//如果j枚举到了i的最小质因子primes[j]，就退出循环，防止重复筛选
                                    //因为j是从0开始枚举的，所以当i % primes[j] == 0时，primes[j]一定是i的最小质因子，并且s[ primes[j]*i ]中的primes[j]*i的最小质因子也是primes[j]
                                    //当i % primes[j] != 0时，原因一定是还没有枚举到i的最小质因子，此时的primes[j]一定小于i的最小质因子，但此时s[ primes[j]*i ]中的primes[j]*i的最小质因子也一定是primes[j]
        }
    }
}

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