Returns the number of primes before int N. This is my implementation of a programming internship practice test problem from some game company. I used the sieve of eratosthenes I saw on wiki once.

NumberOfPrimes

// Nathan Park
// 
// This is my implementation of a programming intership practice test problem
// from some company. 

#include <vector>

int getNumberOfPrimes(int N)
{
  std:vector <int> primes(N, 1); // 0 = prime, 1 means not prime
  for (unsigned i = 2; i < N; ++i)
  {
    if (!primes[0]) continue;
    for (unsigned j = 2; j <= N/i; ++j)
      primes[j * i] = 0;
  }

  unsigned count = 0;
  for (unsigned i = 2; i < N; ++i)
    count += primes[i];

  return count;
}