// Populate prime numbers using wheel factorization
// Algorithm should be fast enough to print 10001st prime number in less than 2 second
// (Before encountering timeout on codepad)
// 10001st prime number is 104743
// Is it possible to write a code that can print 9,99,999th prime number?
#include <iostream>
#include <vector>
using namespace std;

/**
 * This function prints all prime numbers from 2 to upTo.
 *
 * @param [in] upTo Largest number to test for prime.
 */
void printPrimes(int upTo) {
  if(upTo < 2) return;
  vector<int> primes;
  primes.reserve(upTo / 8);
  primes.push_back(2);
  cout << 2 << endl;
  if(upTo > 2) {
    primes.push_back(3);
    cout << 3 << endl;
  }
  int limit = 2, nextsq = 3 * 3;
  for(int i = 5; i <= upTo; i += 2) {
    if(nextsq <= i + 2) {
      ++limit;
      const int s = limit + 1;
      nextsq = s * s;
    }
    for(vector<int>::iterator it = primes.begin(); *it <= limit; ++it) {
      if(0 == i % *it) goto skipped;
    }
    primes.push_back(i);
    cout << i << endl;
skipped: i += 2;
    for(vector<int>::iterator it = primes.begin(); *it <= limit; ++it) {
      if(0 == i % *it) goto skipped2;
    }
    primes.push_back(i);
    cout << i << endl;
skipped2: i += 2;
  }
}

int main(int argc, char *const *argv) {
  if(1 == argc) {
    printPrimes(112233);
  } else for(int i = 1; i < argc; ++i) {
    printPrimes( atoi(argv[i]) );
  }
  return 0;
}