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]
     {
          cout << 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]
     {
          cout << 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!

 

[LudusRex]

Hello,

This algorithm is used to identify prime numbers within a given range (in this case, from 2 to N). The boolean array is used to keep track of whether a number is prime or not. Let's go through the steps to understand how it works:

1. First, the array is initialized with N elements and each element is set to true. This means that initially, we assume that all numbers from 2 to N are prime.

2. Next, we assign the value of false to the first element in the array. This is because 0 and 1 are not considered prime numbers.

3. The next step is where the main part of the algorithm begins. We start a loop with the variable i, starting from 2 (since we have already eliminated 0 and 1 as prime numbers). This loop will continue until i reaches the value of N.

4. Inside this loop, we check if the current element in the array (table) is true. If it is true, it means that i is a prime number. We then print out the value of i and also initialize a new variable j with a value of 2*i. This is because any multiple of i (2*i, 3*i, 4*i, etc.) will not be a prime number. For example, if i is 2, then 2*2, 2*3, 2*4, etc. will all be non-prime numbers.

5. We then start another loop with the variable j, which will continue until it reaches the value of N. Inside this loop, we set the value of table[j] to false. This means that we are marking all the multiples of i as non-prime numbers.

6. Once this loop is completed, we increment the value of i by 1 and the process is repeated until i reaches the value of N.

7. Finally, if you notice, the count variable is not used in this algorithm. It seems to be just a leftover from previous versions of the code and can be removed.

In summary, this algorithm works by iterating through all the numbers from 2 to N and marking all the multiples of each number as non-prime numbers. This way, at the end of the algorithm, all the elements in the array that are still true will represent prime numbers.

I hope this helps explain the algorithm. Let me know if you have any further questions.