线性筛质数
原题链接:868. 筛质数 - AcWing题库
解题思路
埃氏筛质数有部分有一些如33 = 3 * 11的数会被11和3两个数重复算了,说明有一部分部分被重复算了,所以就有了线性筛法。
因为算术基本定理——任何一个大于1的自然数可以分解成一些质数的乘积。且表示方式唯一。所以我们可以用一个数的最小质因数去筛这个数。这样就不会有重复。
一下是详细思路
for(int i = 2;i <= n;i ++)//枚举从1-n的数
{
if(!st[i])prime[++ cnt] = i;//经过前面的剔除和数这个数还没有被确认为和数这个数就是质数
//(要得到自然数n以内的全部素数,必须把不大于sqrt\(n)的所有素数的倍数剔除,剩下的就是素数)
for(int j = 1;prime[j] <= n / i/*因为我们只需要筛掉n以内的和数所以只用遍历到n/i*/;j ++)//遍历质数数组中的质数,这个质数prime[j]会与i相乘去筛掉质数
{
st[prime[j] * i] = true;//计算和数
if(i % prime[j] == 0)break;//因为质数数组是从小到大遍历的所以如果i被prime[j]整除说明prime[j]是i的最小质因子
//所以下一轮的i*prime[j+1]和以后几轮的最小质因子就不是prime[j+1]了,而是i的最小质因子prime[j]
//这样违背了线性筛质数用最小质因子筛的原理,所以肯定会有重复就应该break
}
}
源代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1000010;
int main()
{
bool st[N];//i是不是和数
int prime[N];//记录质数
int cnt = 0;//质数个数
int n;
scanf("%d",&n);
for(int i = 2;i <= n;i ++)
{
if(!st[i])prime[++ cnt] = i;//记录质数
for(int j = 1;prime[j] <= n / i;j ++)
{
st[prime[j] * i] = true;//计算和数
if(i % prime[j] == 0)break;//筛下一个用的就不是最小质因子了所以break
}
}
printf("%d",cnt);
}