AcWing 868. 筛质数
原题链接
简单
作者:
兜兜里有糖_89
,
2024-02-19 14:53:18
,
所有人可见
,
阅读 20
线性筛法在埃氏筛法的基础上进一步优化的理解
- 首先由一个数x的倍数 x * 2 x * 3 ....x * n得到的数一定是一个合数
- 如果 a 能整除 b, 那么 a也能整除 (a * b)
- 一个合数一定能因式分解乘最小质因数的幂次乘积形式,即一个合数一定能被其最小质因子,所以只需要用最小质因子去筛掉合数
#include<iostream>
using namespace std;
typedef long long ll;
const ll M = 2e9+10; //太大了
const int N = 1e6+10;
bool st[N];
int primes[N];
int n;
int cnt;
// 只让合数的最小质因数筛掉这个合数,减少多次判断
void get_primes(int n)
{
for(int i = 2; i <= n; i++)
{
if(!st[i]) primes[cnt++] = i; // 如归是质数就加进primes数组
// 遍历primes
for(int j = 0; primes[j] * i <= n; j++) // primes[j] * i是一个合数同时保证不超过n
{
// 筛掉最小质因数的倍数
st[primes[j] * i] = true;
// 由于每一次内循环是从小到大遍历primes数组,则质数就会与i=2、3、..相乘得到合数,只要i % primes[j] !=0(i不能整除这个素数) 就能保证当前primes[j]是primes[j]*i的最小的质因数
// 由算数基本定理,则primes【j】也是primes[j] * i的最小质因数,例如primes[j] = 2, i = 4, 2是4的最小质因数,同时2也是8的最小质因数
// 于是就能保证每一次primes[j] * i是用最小质因子primes[j]得到的合数并筛掉
// 如果i能整除primes[j]这个质数就应该终止内循环遍历primes数组,因为primes【j+1】*i一定能被primes[i] * 某个数筛掉,实质上是减少了用所有质数去筛其倍数的判断,只用最小质因子去筛合数
if(i % primes[j] == 0)
{
break;
}
}
}
}
int main()
{
cin>>n;
get_primes(n);
cout<<cnt;
return 0;
}