Sieve of Erathostenes

erathostenes.cpp

vi primes;
bool prime[1000100];

void generatePrimes(int n) {
      for (int i = 2; i * i <= n; i++)
         if (prime[i])
            for (int j = i * i; j <= n; j += i)
               prime[j] = false;
      int cnt = 0;
      for (int i = 2; i <= n; i++)
         if (prime[i])
            primes.pb(i);
}