Sieve of Erathostenes

Primes

If we wished to find the 10,000 prime, how big would our table need to be?
Another method would be to only put primes into our table.
If we loop through the odd numbers from 3 to N, a number is prime if it not a multiple on any prime in out table.
Start with 2 and 3 in our table.

2 3 ...
5 goes into the table because it is not a multiple of 2 or 3.

2 3 5 ...
7 goes into the table because it is not a multiple of 2, 3 or 5.

2 3 5 7 ...
9 does not go into our table because it is divisible by 3.
We repeat this process until we compute the desired number of primes.

Output

Computed Primes are
1000    7927
2000    17393
3000    27457
4000    37831
5000    48619
6000    59369
7000    70663
8000    81817
9000    93187
10000   104743
11000   116461
12000   128201
13000   139907
14000   151717
15000   163847
16000   176087
17000   187973
18000   200191
19000   212383
20000   224743
Press any key to continue . . .

Code

//
// primes
//
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
   const int COUNT = 20001;
   int  numbers[COUNT];
   int  candidate;
   int  primes;
   bool isprime;
  
   numbers[0]=2;  // first even prime
   numbers[1]=3;  // first odd prime
   primes=2;      // I have two primes
   candidate=5;
   while(primes < COUNT) {
     isprime=true;
     for(int index=0 ; index < primes && isprime; index++)
       if(candidate % numbers[index] == 0 ) isprime=false;
     if(isprime) {
       numbers[primes]=candidate;
       primes++;
     }
     candidate+=2;
   }
   //
   // print every 1000 th prime number
   //
   cout << "Computed Primes are " << endl;
   for(int index=1000; index < 20001; index+=1000)
     cout << index << "\t" << numbers[index] << endl;

   system("pause");
   return 0;
}