AcWing 868. 筛质数(详细注释版)
原题链接
简单
作者:
Vincent_AC
,
2021-01-06 22:06:57
,
所有人可见
,
阅读 585
- 朴素做法:首先先把所有的数写到数表中去,然后把每一个数所有的倍数删掉,筛选完后所有剩下的数就是质数,时间复杂度:o(nlogn)。
- 质数定理:从1~n中有$\frac{n}{\ln n}$个质数。
- 埃氏筛法:在所有的质数中进行朴素的做法,时间复杂度:o(nloglogn)。
- 线性筛法的核心思路:每一个数n只会被它的最小质因子筛掉。注意点:在做乘法的时候即使单个变量在int范围内,如果乘积超了int那么也会出错。
- 补充知识:
(1)整数唯一分解定理:任何一个大于1的自然数N,如果N不为质数,都可以唯一分解成有限个质数的乘积$N={P_1}^{a_1}\times{P_2}^{a_2}\times{P_3}^{a_3}\times…\times{P_n}^{a_n}$,这里的${P_1}<{P_2}<{P_3}<…<{P_n}$均为质数,其中指数$a_i$是正整数。
(2)线性筛是在埃氏筛法的基础上,让每一个合数,只被它的最小质因子筛选一次,达到不重复的目的。根据整数的唯一分解定理,每个合数有且只有一组质数相乘可以得到,前面的埃氏筛法,每一个质因子都要筛掉该合数一次,我们如果让每个合数只被它最小的质因子筛选就完全避免了埃氏筛法的重复。从算法来说,每一个质因子都要筛掉该合数一次,我们如果让每个合数只被它最小的质因子筛选就完全避免了埃氏筛法的重复。从算法来说,N范围内的每个数都只会被筛一次,所以算法复杂度是O(n)。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
/*
* st[j]表示j是否被筛掉,st[j] = true表示j被筛掉一定不是素数
* st[j] = false表示没有被筛掉,是素数
*/
bool st[N];//放在堆中已经初始化为0了,也就是false
//朴素筛法-O(nlogn)
void get_primes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i])
{
//若n之前1~i-1所有的倍数都不含i,那么i就是质数
primes[cnt ++] = i;
}
//把每一个数全部筛一次
for (int j = i + i; j <= n; j += i)//i所有的倍数均不是质数,删掉
st[j] = true; //表示j一定不是质数
}
}
//埃氏筛法-O(nloglogn)
void get_primes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i]) //i没有被标记过,!st[i]=true
{
//若n之前1~i-1所有的倍数都不含i,那么i就是质数
primes[cnt ++] = i;
//仅仅筛质数
for (int j = i + i; j <= n; j += i)//i所有的倍数均不是质数,删掉
st[j] = true; //表示j一定不是质数
}
}
}
//线性筛法-o(n)
void get_primes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i]) //若i是质数
primes[cnt ++] = i; //数组中的质数从小到大
//j是从小到大枚举所有的质数
//primes[j]一定是小于等于n的最小质因子,所以其合数i*primes[j]也应该是小于等于n的
//因此就是primes[j]*i <=n,但是乘积可能会爆int,所以写成primes[j] <= n / i
for (int j = 0; primes[j] <= n / i; j ++)
{
//i*primes[j]也就是质数prime[j]作为最小质因子能够筛掉的部分合数
st[primes[j] * i] = true;
//满足这个式子,primes[j]一定是i的最小质因子
if (i % primes[j] == 0)
break;
}
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}