题目描述

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

样例

输入:8
输出:4
//========================================
筛法一:试除法

1. 思想:试除法(判断2~n中每个数是不是质数)
2. 时间复杂度:O(n*n)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int res;
bool is_prime(int n){
    if(n<2) return false;
    for(int i=2;i<=n/i;i++){
        if(n%i==0) return false;
    }
    return true;
}
int main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        if(is_prime(i)) res++;
    }
    cout<<res<<endl;
    return 0;
}

筛法二:朴素筛法
1. 思想:遍历2~n(下标为i),将所有i的倍数删掉
2. 时间复杂度:O(nlog(n))

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010;
int n;//2~n
int primes[N],cnt;//质数数组+质数个数
bool st[N];//用来删除数的bool数组
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=i;j<=n;j+=i){
            st[j]=true;
        }
    }
}
int main(){
    cin>>n;
    get_primes(n);
    cout<<cnt<<endl;
    return 0;
}

筛法三:埃氏筛法
1. 思想:遍历2~n中”所有的质数”(下标为i),将i的倍数删掉
2. 时间复杂度:O(nlog(log(n)))

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010;
int n;//2~n
int primes[N],cnt;//质数数组+质数个数
bool st[N];//用来删除数的bool数组
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i){//删掉所有质数的倍数
                st[j]=true;
            }
        } 
    }
}
int main(){
    cin>>n;
    get_primes(n);
    cout<<cnt<<endl;
    return 0;
}

筛法四:线性筛法
1. 思想:遍历2~n中(下标为i)i的最小值因子(primes[j]),将i*primes[j]删掉
2. 时间复杂度:O(n)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010;
int n;//2~n
int primes[N],cnt;//质数数组+质数个数
bool st[N];//用来删除数的bool数组
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;//因为是从小到大枚举所有质因子,所以primes[j]一定是i*primes[j]的最小质因子
            if(i%primes[j]==0) break;
        }
    }
}
int main(){
    cin>>n;
    get_primes(n);
    cout<<cnt<<endl;
    return 0;
}