题目描述

线性筛法：任何一个合数都会被筛掉，且用它的最小质因子去筛，所以是线性的
核心：每一个数n只会被他的最小质因子筛掉。

1. i%pj == 0 break时 pj 一定是 i 的最小质因子
   所以 pj 也一定是 i*pj 的最小质因子
2. i%pj ！= 0 时 pj 一定小于 i 的所有质因子
   所以 pj 也一定是 pj*i 的最小质因子

合数一定会被筛掉：
对于一个合数 x 一定存在一个最小质因子，假设他是pj
当 i 枚举到 x/pj 时 x 一定会被筛掉(筛的终止条件 i<=x/pj 或 pj <= x/i )

C++ 代码

#include<iostream>

using namespace std;

const int N=1e6+5;

int n;
bool st[N];
int prime[N],cnt;

void get_primes(int n)
{//朴素筛法 O(n lnn)
    //优化：只筛质数的倍数 约等于O(n),严格是O(n loglogn) 称为埃氏筛法
    if(n<2)return;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]){
            prime[cnt++]=i;
            for(int j=i+i;j<=n;j+=i)st[j]=true;
        }

        //for(int j=i+i;j<=n;j+=i)st[j]=true;
    }
}

void get_primes2(int n)
{//线性筛法，时间复杂度O(n), 当数据达到10^7 时，效率大致比埃氏筛法快一倍
    for(int i=2;i<=n;i++)
    {
        if(!st[i]){
            prime[cnt++]=i;
        }

        for(int j=0;prime[j]<=n/i;j++){//
            st[prime[j]*i]=true;
            if(i%prime[j]==0)break;//pj一定是i的最小质因子
        }
    }
}

int main()
{
    cin>>n;
    get_primes2(n);
    //for(int i=0;i<cnt;i++)
    //    cout<<prime[i]<<" ";
    cout<<cnt<<"\n";
    return 0;
}