PrimeChecker

class PrimeChecker{
    private: vector<int> num;

    public: PrimeChecker(int maxn = 10000001){
        num = vector<int>(maxn + 1 , 0);
        num[0] = num[1] = 1;
        for(int i = 2 ; i <= maxn ; ++i){
            if(!num[i]){
                for(int j = i * 2 ; j <= maxn ; j += i){
                    num[j] = 1;
                }
            }
        }
    }

    bool isPrime(int t){
        if(t >= num.size()){
            for(int i = 2 ; i * i <= t ; ++i){
                if(t % i == 0){
                    return 0;
                }
            }
            return 1;
        }
        return !num[t];
    }
};

/*
int n;
    cin >> n;

    PrimeChecker pr = PrimeChecker();
    repf(i , 2 , n + 1){
        if(pr.isPrime(i))cout << i << " ";
    }
*/