数学知识 筛质数

筛质数

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

输入格式
共一行，包含整数 n。

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

数据范围
1≤ n ≤10⁶
输入样例：

8

输出样例：

4

筛选n以内的质数：

朴素筛法：O(nlogn)
i 从 2 开始遍历，把 n 以内所有 i 的倍数全部筛选掉，剩下的数就是质数。

void get_primes(int n)
{
for(int i=2;i<=n;i++) //p存放已经找到的质数，cnt记录已经找到的质数的数量
{
if(!st[i]) p[cnt++]=i;//把质数存起来
for(int j=2;j<=n/i;j++) //把所有i的倍数筛选掉（不是质数）
st[i*j]=1;
}
}

埃氏筛法：O(nloglogn)
在筛选过程中只需要筛选掉质数的倍数即可。（唯一分解定理：每个大于1的自然数都可以写成是两个以上的质数的成积）

void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])
{
p[cnt++]=i;
for(int j=2;j<=n/i;j++) st[i*j]=1;
}
}
}

线性筛法：O（n）
任何一个合数都能唯一分解为有限个质数的乘积，除去这其中最小的质因数，其他的都乘起来就是最大因数。而线性筛法的核心思想就是用最小的质因数一次筛选掉合数。

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int st[N],p[N];
int n,cnt;
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) p[cnt++]=i;
//筛掉已知的质数与i的乘积
//条件相当于p[j]*i<=n
for(int j=0;p[j]<=n/i;j++)
{
st[p[j]*i]=1;
/*
1.i%pj==0 pj一定是i的最小值最小质因子，pj一定是pj*i的最小质因子
2.i%pj!=0 pj一定小于i的所有质因子，pj也一定是pj*i的最小质因子。
*/
if(i%p[j]==0) break;
//筛选掉以p[j]为最小质因数的数(p[j]*i)，（此时i为对应的最大质因数，这样的数对只有一对）。
//以 2，3，4，5，6，7，8，9，10，11，12为例。
//当 i=4 时，此时的已知的质数有2，3
//2和4分别是2*4=8的最小和最大质因数，但是3*4=12的最小最大质因数是2*6，跳出循环
//跳出循环就可以避免重复查找到合数的情况，使筛选变成线性的。
}
}
}
int main()
{
cin>>n;
get_primes(n);
cout<<cnt<<endl;
return 0;
}

最后

以上就是潇洒流沙为你收集整理的数学知识 筛质数的全部内容，希望文章能够帮你解决数学知识 筛质数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。