算法笔记。质数筛算法

题目：

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

输入格式

共一行，包含整数 n。

输出格式

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

数据范围

1≤n≤106

输入样例：

8

输出样例：

4

埃式筛：

思路:

将所有质数的倍数筛除

代码实现：

#include <iostream>
#include <vector>
using namespace std;
const int N = 1000100;int n;
bool st[N];
vector<int> v;int main()
{cin>>n;for(int i = 2;i<=n;i++){if(!st[i])//如果没有被筛除，就是质数{v.push_back(i);//添加质数for(int j = i;j<=n;j+=i) st[j] = true;//筛除所有质数的倍数}}cout <<v.size();return 0;
}

参考：

入门算法课(4)-质数和筛法 | 质数 | 埃氏筛 | 线性筛 | 二次筛法 | 编程 | 算法竞赛 | 数学_哔哩哔哩_bilibili

线性筛：

代码实现：

#include <iostream>
#include <vector>
using namespace std;
const int N = 1000100;int n;
bool st[N];
vector<int> v;int main()
{cin>>n;for(int i = 2;i<=n;i++){if(!st[i]) v.push_back(i);//加入质数for(int j = 0;v[j]<=n/i;j++) {st[v[j]*i] = true;//筛除非质数if(i%v[j] ==0) break;//最多筛除到v中最后一个质数的平方}}cout <<v.size();return 0;
}

 思路：

参考：入门算法课(4)-质数和筛法 | 质数 | 埃氏筛 | 线性筛 | 二次筛法 | 编程 | 算法竞赛 | 数学_哔哩哔哩_bilibili