题目描述

blablabla

样例

blablabla

算法1

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>

using namespace std;

const int N=1e6+10;

int prime[N],cnt;

bool st[N];

void get_prime( int num ){
    for( int i = 2; i <= num; ++i ){
        if(!st[i]) prime[cnt++] = i;
        for( int j = 0; prime[j] <= num/i; ++j ){
            st[ prime[j] * i ] = true;
            if( i % prime[j] == 0 )//出现了某一质数的倍数，直接跳出以简化流程
                break;
        }
    }
}

int main(){
    int n,c;
    cin>>n;
    get_prime(n);
    cout<<cnt;
    return 0;
}