TIOJ 1036 How Many Primes?

一開始看成10^8....

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

char seive[1300000] = {0};

int sum[10000001] = {0};

inline void setb(int n){ seive[n>>3] |= 1<<(n&7); }

inline bool getb(int n){ return seive[n>>3]&(1<<(n&7)); }

int main(){

    setb(0), setb(1);

    for(int lx = 2;lx < 10000000;++lx)

        if(getb(lx) == 0)

            for(int ly = 2;ly*lx <= 10000000;++ly)

                setb(ly*lx);

    sum[0] = 0;

    for(int lx = 1;lx <= 10000000;lx++)

        sum[lx] = sum[lx-1] + (getb(lx) == 0);

    int m; scanf("%d", &m);

    for(int lx = 0;lx < m;lx++){

        int poi; scanf("%d", &poi);

        printf("%d\n", sum[poi]) ;

    }

    return 0;

}