题目描述

求1~n内的质数个数

朴素算法

时间复杂度 $O(nlogn)$

C++ 代码

#include<iostream>
using namespace std;
const int N=1e5+10;
bool st[N],primes[N];
int main()
{
    int n,cnt=0;
    cin>>n;
    for(i=2;i<=n;i++)
    {
        if(st[i]) continue;
        primes[cnt++]=i;
        for(j=i+i;j<=n;j+=i)
            st[j]=true;
    }
    cout<<cnt<<endl;

}

线性筛法

$O(n)$

时间复杂度

C++ 代码