题目描述
给定一个正整数 n,请你求出 1∼n 中质数的个数。
输入格式
共一行,包含整数 n。
输出格式
共一行,包含一个整数,表示 1∼n 中质数的个数。
数据范围
1≤n≤106
样例
输入样例:
8
输出样例:
4
算法1
题目给定一个数n,要求给出1~n中质数的个数。
第一种方法是暴力做法,原理非常简单:
如果一个数是另一个数的倍数,那么这个数一定是合数,那么我们把每一个从2~n的数的倍数都筛掉,最后剩下的一定是质数。
关键变量:
bool state[N];用于表示数字是否被筛掉,1为筛掉(合数),0为不筛掉(质数)
int count;表示质数的个数
C++ 代码
#include <iostream>
using namespace std;
const int N = 1000010;
int count;
bool state[N];
void get_primes(int n){
for(int i = 2;i<=n;i++){
if(state[i]==0){
count++;
//对质数进行计数
}
for(int j = i+i;j<=n;j+=i){
state[j]=true;
}//对每一个数都进行倍数筛选
}
}
int main(){
int n;
cin>>n;
get_primes(n);
cout<<count;
}
算法2
埃氏筛法,是古希腊数学家埃拉托色尼提出的一种筛选法。
埃氏筛法的核心思想:
只需要使用所有的素数进行筛选就可以完成任务。
在上一种暴力做法中,我们对2~n中的所有数字,都进行了倍数的筛选,这其实是可以进行优化的。
优化原理
无需对合数进行倍数筛选,因为合数以及合数的倍数,一定可以被质数筛选掉。
因此我们只需要对所有的质数进行筛选就足够了。
C++ 代码
#include <iostream>
using namespace std;
const int N = 1000010;
int count;
bool state[N];
void get_primes(int n){
for(int i = 2;i<=n;i++){
if(state[i]==0){
count++;
for(int j = i+i;j<=n;j+=i){
state[j]=true;
}
}
}
}
int main(){
int n;
cin>>n;
get_primes(n);
cout<<count;
}
算法3
线性筛法
其实本题的核心思想就是要通过各种不同的方法,把每一个合数都删掉,每一个方法都能够做到,只不过时间复杂度有高有低。普通的方法,一个合数会被筛掉好几次,造成时间比较长。
而线性时间的筛法,在O(n)内完成筛选。
核心思想
1、每一个合数都有唯一一个最小质因数。
2、每一个合数都能被筛到。
3、每一个合数都只能被它的最小质因数筛掉,且只会被筛一次。
证明
1、易证
2、本题的关键变量是primes[j]i,这个数是一个合数,primes[j]是质数,i遍历的范围是2~n。
那么,primes[j]i,能否取到2~n中的所有合数?显然是可以的。因此每一个合数都可以被遍历到
3、每一个合数都可以被primes[j]*i的两层循环遍历到,并且,primes[j]是primes[j]*i的最小质因数,
证明:
当i%pj不为零,pj小于所有i的质因子,并且pj是pj本身的最小质因子。因此,pj是ipj这个合数的最小质因子。
当i%pj为零,因为pj是从小到大被枚举的,因此pj就是i的最小质因子,并且pj是pj本身的最小质因子。因此,pj是ipj这个合数的最小质因子。
为什么要break
整除之后,primes[j]就是i的因数,所以下一次循环primes[j+1]就不再是p[j+1]*i的最小质因数,因为primes[j+1]>primes[j]。所以应该break,不然如果继续循环的话,会抢了primes[j+1]*i的最小质因数的工作,一个数会筛两遍。
及时break确保了每个合数只会被自己的最小质因数给筛掉。
核心代码
void get_primes(int n){
for(int i = 2;i<=n;i++){
if(state[i]==0) {
primes[count]=i;//把质数从小到大加入primes数组
count++;
}
for(int j = 0;primes[j]<=n/i;j++){//从小到大遍历质数
state[primes[j]*i] = true;//筛掉primes[j]*i,可证明primes[j]是primes[j]*i的最小质因数
if(i%primes[j]==0)break;//整除之后,primes[j]就是i的因数,primes[j+1]就不再是pj+1*i的最小质因数。
}
}
}
C++ 代码
#include <iostream>
using namespace std;
const int N = 1000010;
int count;
bool state[N];
int primes[N];
void get_primes(int n){
for(int i = 2;i<=n;i++){
if(state[i]==0) {
primes[count]=i;
count++;
}
for(int j = 0;primes[j]<=n/i;j++){
state[primes[j]*i] = true;
if(i%primes[j]==0)break;
}
}
}
int main(){
int n;
cin>>n;
get_primes(n);
cout<<count;
}