Prime Numbers Generator in Liner Time

prime_number_generator.cpp

#include <iostream>
#include <vector>

const int MAX = 2000000;

bool is_prime[MAX + 1] = { 0 };
std::vector<int> primes;

int main() {
  is_prime[2] = true;
  for (int i = 2; i <= MAX; i++) {
    if (!is_prime[i])
      primes.push_back(i);

    for (size_t j = 0; j < primes.size(); j++) {
      if ((long long)primes[j] * i > MAX)
        break;
      is_prime[primes[j] * i] = true;
      if (i % primes[j] == 0)
        break;
    }
  }

  std::cout << primes.size() << std::endl;
}
/*
# Test result

Cheng@CHENG-PC ~/Desktop
$ time a
227431

real    0m0.187s
user    0m0.015s
sys     0m0.062s
*/