SRM307 div2 difficult

実践では1000000のときの数が分からないので、MAX = 5200000とかいうことはできないと思ってもよい。

#define MAX 12924368  //これを超えたらbad_allocがでた。最大値でも1.90sくらいで間に合う。
int preprime[MAX] = {0};

//エラトステネスを改良。
class PreprimeNumbers {
public:
  int nthNumber(int n) {
    for(int i = 2, count = 0; i < MAX; i++) {
			int tmp = (int)cbrt(i+0.5);
      if(fabs(cbrt(i) - tmp) < eps && preprime[tmp] == 0) {
				count++;
      } else {
//preprime[i]が0でないなら素数ではないから、preprime[i]*(整数倍)はpreprimeではない。
//計算が無駄になるので、その時は計算を飛ばす。
//具体的には、preprime[i] == 1のとき、preprime[i*j] > 4にして、
二度とfor文を使わないようにすればいいんじゃない？ということ。
				int flag = (preprime[i] == 0) ? 1 : 3;
				if(preprime[i] <= 1) {
					for(int j = i*2; j < MAX; j += i) {
						preprime[j] += flag;
					}
				} 
				if(preprime[i] == 2) count++;
			}
			if(count == n) return i;
    }
    return -1;
  }