#include <iostream>
using namespace std;
const int N = 1e6+10;
int prime[N], cnt;
bool st[N];
//朴素筛法-O(nlogn)
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) prime[cnt++] = i;
for(int j = i+i; j <= n; j += i)
st[j] = true;
}
}
//埃式筛法-O(nloglogn)
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]){
prime[cnt++] = i;
for(int j = i; j <= n; j += i)
st[j] = true;
}
}
}
//线性筛法-O(n), n = 1e7的时候基本就比埃式筛法快一倍了
//算法核心：x仅会被其最小质因子筛去
void get_prime(int x) {
for(int i = 2; i <= x; i++) {
if(!st[i]) prime[cnt++] = i;
for(int j = 0; prime[j] <= x / i; j++) {
//对于任意一个合数x，假设pj为x最小质因子，当i<x/pj时，一定会被筛掉
st[prime[j]*i] = true;
if(i % prime[j] == 0) break;
/*
1.i%pj == 0, pj定为i最小质因子，pj也定为pj*i最小质因子
2.i%pj != 0, pj定小于i的所有质因子，所以pj也为pj*i最小质因子
*/
}
}
}
int main() {
int x;
cin >> x;
get_primes(x);
cout << cnt << endl;
return 0;
}
AcWing 868. 筛质数 原题链接 简单
作者：
郡呈
,
2019-08-13 09:35:47
,
所有人可见
,
阅读 9085
郡呈
,
2019-08-13 09:35:47
,
所有人可见
,
阅读 9085
yxc是傻逼！！
？
?
?
?
埃式中这里for(int j = i; j <= n; j += i) 是不是写错了 int j =i+i
是要写成j=i+i 因为i其实是素数 而它的倍数不是
不管是不是素数都筛的是朴素筛，是素数才筛的是埃式筛。
y站长给的朴素筛法模板代码里遇到非素数直接continue，即只有素数的时候才会筛去素数的倍数，这实际上对应的是这个题解的埃氏筛法。
朴素法prime[cnt]=i 换成 cnt 感觉比较好~
我觉得对于任意个一个合数x, 假设pj 为 x 的最小质因子 , 应该是 i <= x/pj 时才应该一定会被筛掉
线性筛的cnt的下标不是从0开始的吗，为什么最后求出的cnt不用加1呀
啊这，建议模拟一下，每筛出来一个素数，cnt加一，从零开始没啥毛病
//朴素筛法-O(nlogn)
void get_primes(int x) {
for(int i = 2; i <= n; i) {
if(!st[i]) prime[cnt] = i;
for(int j = i+i; j <= n; j += i)
st[j] = true;
}
}
void get_primes(int x) { 这一行这里是int n
好的 谢谢提醒 已更正
emm大佬可以解释一下 prime[j] <= x / i 这里为啥是 x/i 吗？？是不是也是和前面的作用一样都是用来优化的？
建议去看一下基础班的视频，这里的pj是最小质因子，i是某一个合数,i*pj一定是满足<=x的。具体的证明你可以看下视频，我给忘了。
哦哦，谢谢
作用的话是用来控制范围的，移项之后式子为
prime[j] * i <= x，也就是st括号里的那个为了数组不越界。如果写乘法的话有可能爆int
好的，谢谢
st[N]数组表示什么？st[j] = true;表示什么意思吖？用来判断是否是素数。st[j]=true代表数字j是素数
我记着false表示素数吧
反正一种状态表示是素数一种表示非素数就行了，没所谓，看自己定义
st[j] = true;
表示j被划去，表示j一定不是素数
哪个朴素筛法里 prime[cnt] = i是不是和 cnt一样的效果？
额，我没有看懂你的问题。
prime[cnt]=i是不是换成cnt也可以
这里的cnt是用来记录素数的个数的，i是用来遍历2~n，借助st数组来判断是否是素数。
我觉得直接写
prime[cnt]=i换成cnt ++ ；也可以吧 大佬们觉得呢但是这样的话是不是就不知道谁是素数了呀，如果有
primes数组的时候，就将素数存到数组里面了，然后遍历数组就可以知道全部素数了。突然又感觉就算是没有primes···数组也可以知道谁是素数，直接遍历st数组，为False的就是素数，大佬们这样可以吗？为啥要加primes```这个数组啊，我自己把自己绕进去了hhhhh我也懵的
hhh神回复
不行呀
具体问题具体分析，这里的题目是为了求出素数的个数。
好的，谢谢
为什么“对于任意一个合数x，假设pj为x最小质因子，当i<x/pj时，一定会被筛掉”？
因为i枚举到x之前,一定会枚举到x/pj,当pj的i倍大于x时自然就会停止筛法.
三倍！
加量不加价，你值得拥有哈哈哈
你的朴素筛法和埃式筛法是不是写成一样的了？
不是的哦.
朴素筛法把从2~n的所有数的倍数都筛了一遍.
埃式筛法仅仅把素数的倍数筛去.
你可以运行两个函数看一下,大概快3~5倍
我看错了 不好意思
没事,问题不大hhh
这个没看懂，可以再解释一下吗？谢谢！
可以看一下两个函数里if判断部分。
哦哦，好滴，我看书上的埃式筛法写的是 for(int j = i+i; j <= n; j += i) 欸，有点迷惑？？
应该是i×i吧 i×i之前的数字 一定已经被筛过了 所以可以优化一下