题型(筛选质数):给定一个正整数n,求2-n中质数的个数
$\color{red}{1.朴素筛法(O(nlogn))}$
核心思想,对于2-n中的每个数,不管其是合数还是质数,都有
is_prime[ki]=false (k=1、2、3、…) 注意ki<=n

代码(C++)

#include<iostream>
#include<cstring>
const int N=1e6+10;
using namespace std;
bool is_prime[N];
int primes[N];
int main()
{
    int n,t=0;
    memset(is_prime,true,sizeof(is_prime));
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i]) primes[t++]=i;
        for(int j=i+i;j<=n;j+=i)
          is_prime[j]=false;
    }
    cout<<t;
    return 0;
}

$\color{green}{2.埃氏筛法(O(nloglogn))}$
核心思想,对于2-n中的每个数,只有当其为质数时,才有
is_prime[ki]=false (k=1、2、3、…) 注意ki<=n && i为质数

代码(C++)

#include<iostream>
#include<cstring>
const int N=1e6+10;
using namespace std;
bool is_prime[N];
int primes[N];
int main()
{
    int n,t=0;
    memset(is_prime,true,sizeof(is_prime));
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i]) 
        {
            primes[t++]=i;
            for(int j=i+i;j<=n;j+=i)
                is_prime[j]=false;
        }
    }
    cout<<t;
    return 0;
}

$\color{blue}{3.线性筛法(O(n))}$
核心思想:用i的最小质因子去筛合数 (i为从2-n中任取的一个正整数)

代码(C++)

#include<iostream>
#include<cstring>
const int N=1e6+10;
using namespace std;
bool is_prime[N];
int primes[N];
int main()
{
    int n,t=0;
    memset(is_prime,true,sizeof(is_prime));
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i]) 
        {
            primes[t++]=i;
        }
        for(int j=0;primes[j]<=n/i;j++)
        {
            is_prime[primes[j]*i]=false;
            if(i%primes[j]==0) break;
        }
    }
    cout<<t;
    return 0;
}

代码解析

   for(int j=0;primes[j]<=n/i;j++)
    {
        is_prime[primes[j]*i]=false;
        if(i%primes[j]==0) break;
    }

①当i%primes[j]==0 $\longrightarrow$ primes[j]为i的最小质因数
$$\color{brown}{∴primes[j]也是primes[j]*i的最小质因子}$$

②当i%primes[j]!=0 $\longrightarrow$ primes[j]小于i的最小质因数
(why? primes数组中存放的质数 按从小到大的顺序存放)
$$\color{brown}{∴primes[j]也是primes[j]*i的最小质因子}$$

$$\color{brown}{综①②所得,无论i\%primes[j]!=0\quad||\quad i\%primes[j]==0都有primes[j]=primes[j]*i的最小质因子}$$

$\color{red}{线性筛法的核心思想:用i的最小质因子去筛合数}$
$$\color{brown}{∴当枚举完i的最小质因数后跳出循环这一操作}$$