线性法筛质数

线性是因为 素数数组prime中的每个数只会被遍历一次
每个合数只会被其最小质因子删去

题目描述

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

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

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

数据范围
1≤n≤10^6

输入样例：
8
输出样例：
4

1.为什么可以利用prime[j]作为最小质因子来删去合数prime[j] * i

代码运行会有俩种情况
① i % prime[j] == 0
由于prime[j]是由小到大进行遍历的
所以此时找到的第一个能被i整除的prime[j]一定就是i的最小质因子
② i % prime[j] != 0
由于prime[j]是由小到大进行遍历的
说明此时 prime[j] 小于i的最小质因子
所以prime[j] * i的最小质因子是prime[j]

prime[j] * i的最小质因子 = min(prime[j],i的最小质因子)

2.为什么prime[j] <= n / i;

数的范围是1 ~ n ,所以我们要判断的合数范围也到n即可
此式写成 prime[j] * i <= n会好理解一些(但是可能会爆int)
所以可以写成(long long) prime[j] * i <= n

3.为什么当 i % prime[j]时要break

这个算法的俩大原则:

Ⅰ每个合数只会被它的最小质因数筛去

Ⅱ 每个数只会被筛一次

如果我们在 i % prime[j] == 0时没有退出循环
下一次代码会利用 prime[j + 1]来删去prime[j + 1] * i

由 prime[j] * i的最小质因子 = min(prime[j],i的最小质因子)可知
i的最小质因子为prime[j],且prime[j] < prime[j + 1] (prime数是组递增遍历的)

所以prime[j + 1] * i 应该是由prime[j]来将其删去

但此时被prime[j + 1]删去了,违背了原则Ⅰ Ⅱ:
并没有由其最小质因子删去
在prime[j]时被删一次,prime[j + 1]时又删一次

C++ 代码

#include<iostream>
using namespace std;

const int N = 1000010;
int prime[N];
bool st[N];
int cnt, n;

void get_prime()
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt ++] = i;

        //遍历素数数组prime
        for(int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

int main()
{
    cin>>n;
    get_prime();
    cout<<cnt<<endl;
}

这些都是我在学习这里是遇到的困惑和我自己的一些理解
如有错误希望大佬指正