AOJ 0009 Prime Number

皆さんこんばんは。
高専プロコンに追われているchigichanです。
およそ一ヶ月ぶりの更新です。
この一ヶ月の間に見事にCFのratingを大幅に下げましたw

さて、今日はAOJ0009 Prime Numberです。
これはいろいろな解法がありますが、今回はエラトステネスの篩というもので、ときました。

とりあえずコ～ド。

#include<cstdio>
using namespace std;
bool us[1000010]={false};
int p[1000010] = {0};
int main(){
    /*Eratosthenes*/
    p[0] = 2;
    for(int i = 0; i <= 1000010; i+=2){
        us[i] = true;
    }
     
    int cnt = 1;
    for(int i = 3; i <= 1000010; i+=2){
        int q = 0;
        if(us[i] == true)continue;
        else if(us[i] == false){
            p[cnt] = i;
            cnt++;
            us[i] = true;
            q = i;
            for(int j = q+q; j <= 1000010; j += q){
                us[j] = true;
            }
        }
    }
     
    int n;
    while(~scanf("%d",&n)){
        int x = 0;
        while(1){
            if(p[x] > n)break;
            x++;
        }
        printf("%d\n",x);
    }
    return 0;
}

えっと、エラトステネスの篩っていうのは数を小さい方から見ていきながら、その倍数をふるっていく感じです。詳しくはコードを見ればわかると思います。
このアルゴリズムはおよそO(n log log n)と言われています。
まぁ大体O(n)ってことですかね...