Boolean array to identify prime numbers - C++

[sandy.bridge]

Hey guys, just looking for an explanation for the following algorithm. It is in my textbook, and there isn't really an explanation. I don't really see how the algorithm works, but I will add what I do know, and hopefully one of you can help. Thanks.

//this initial declarations produces an array with N elements.
int N = 40;
bool table[N];
int count = 0;

//this while loop assigns every element in the array to true.
int i = 0;
while (i < N)
{
     table[i]=true;
     i=i+1;
}

//from here is where I get lost.
table[0]=false; //assigns false value to the first element in the array.
i=2; //starts the next loop at 2.
while (i < N)
{
     if (table[i]
     {
          count << i << " is prime." << endl;
          int j = 2*i;

          while (j < N)
          { 
              table[j]=false;
               j=j+i;
          }
     }
i=i+1;
}

Furthermore, I am not entirely sure why count was initialized at the beginning of the algorithm, I never saw it used.

 

[Hurkyl]

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

 

[trollcast]

Hey guys, just looking for an explanation for the following algorithm. It is in my textbook, and there isn't really an explanation. I don't really see how the algorithm works, but I will add what I do know, and hopefully one of you can help. Thanks.

//this initial declarations produces an array with N elements.
int N = 40;
bool table[N];
int count = 0;

//this while loop assigns every element in the array to true.
int i = 0;
while (i < N)
{
     table[i]=true;
     i=i+1;
}

//from here is where I get lost.
table[0]=false; //assigns false value to the first element in the array.
i=2; //starts the next loop at 2.
while (i < N)
{
     if (table[i]
     {
          count << i << " is prime." << endl;
          int j = 2*i;

          while (j < N)
          { 
              table[j]=false;
               j=j+i;
          }
     }
i=i+1;
}

Furthermore, I am not entirely sure why count was initialized at the beginning of the algorithm, I never saw it used.

Its basically an implementation of the sieve of eratosthenes method to find primes.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

The boolean array, table, keeps track of a boolean value for every number up to N that tells whether that number is prime or not. The code then starts from the first prime (2) and excludes all multiples of 2 by setting their boolean value to false. Then the next lowest true value is obviously the next prime, then it repeats this for this number and excludes all its multiples in the table. So then it keeps repeating this process until it reaches the end of the array.

 

[sandy.bridge]

Perfect, thanks!