Prime Numbers

• 05-28-2007
EdSquareCat
Prime Numbers
Prime Numbers 2 - 1000

Code:

```#include <iostream> using std::cout; using std::cin; using std::endl; int main() {     int array_size = 1000;     bool num[ array_size ];     for ( int a = 2; a < array_size; a++ )  // Set all elements to 1     {         num[ a ] = 1;     }     for ( int b = 2; b < array_size / 2; b++ )     {         if ( num[ b ] == 1 )         {             for ( int c = b; c < array_size; c + b )             {                 num[ c ] = 0;             }         }     }        for ( int d = 2; d < array_size; d++ )     {         if ( num[ d ] == 1 )         {             cout << d << endl;         }     }     cin.get();     return 0; }```
No output.
Maybe the fact that it's 2 am whenever I try to do a question in the book doesn't help.
• 05-28-2007
anon
Code:

```for ( int b = 2; b < array_size / 2; b++ )     {         if ( num[ b ] == 1 )         {             for ( int c = b; c < array_size; c + b ) //Does not change c             {                 num[ c ] = 0;             }         }     }```
My other guess is that this will try to set the whole array to false.
• 05-28-2007
EdSquareCat
EDIT:

Code:

```#include <iostream> using std::cout; using std::cin; using std::endl; #include <iomanip> using std::setw; int main() {     int array_size =1000;     bool num[ array_size ];     int counter = 0;     for ( int a = 2; a < array_size; a++ )  // Set all elements to 1     {         num[ a ] = 1;     }         num[ 2 ] = 0;     for ( int b = 2; b < array_size / 2; b++ )  // Multiply all numbers from 1 to 500     {         if ( num[ b ] == 0 )         {             for ( int c = b; c < array_size; c += b )  // Eliminate multiples             {                 num[ c ] = 0;             }         }     }        for ( int d = 2; d < array_size; d++ )  // Display     {         if ( num[ d ] == 1 )         {             cout << setw( 5 ) << d;                         if ( counter &#37; 10 == 1 )                 cout << endl;                         counter++;         }     }     cin.get();     return 0; }```
Nevermind, I got it right I just have some formatting issues.

Edit:
1 error: 999 comes out as prime!

In my output, why are the first 2 numbers alone? (The rest is fine)

Code:

```5  7 7  9  11  13 ...... etc```
• 05-28-2007
Salem
> why are the first 2 numbers alone?
Either the start value for counter is wrong, or you're testing the wrong result.
• 05-28-2007
anon
The formating looks like this, because the first time you print the newline, counter is 1 (1&#37;10=1).

The sieve itself as it is finds odd numbers - not primes at all.

Firstly you might use the keywords true and false (instead of 1 and 0) for the num array. Then decide what they stand for. It seems the value true (after the sieve) indicates that it is a prime.

Don't mark 2 as a non-prime (0).
In the loop, if you find a prime (that hasn't been marked as non-prime this far), mark all the values starting from (b+b) as non-primes (but not the number itself!).

b*b should also be a good starting value for marking non-primes, e.g for 3 you won't need to start marking non-primes at 6 which is already marked, but at 9 = 3*3. Similarly for 5, 10 is already marked as 2*5, 15 as 3*5 and 20 as 2*2*5 - hence 25 is the first number to mark.
• 05-28-2007
robatino
Should be
Code:

`  const int array_size = 1000;`
as standard C++ doesn't allow variable-length arrays.
• 05-28-2007
EdSquareCat
Oh crap your right, its just odd numbers. I made a typo with true/false. My original output was prime numbers from 503 to 997:
Code:

```#include <iostream> using std::cout; using std::cin; using std::endl; #include <iomanip> using std::setw; int main() {     const int array_size = 1000;     bool num[ array_size ];     int counter = 0;     for ( int a = 2; a < array_size; a++ )  // Set all elements to 1     {         num[ a ] = true;     }     for ( int b = 2; b < array_size / 2; b++ )  // Multiply all numbers from 2 to half array size     {         if ( num[ b ] == true )         {             for ( int c = b; c < array_size; c += b )  // Eliminate multiples             {                 num[ c ] = false;             }         }     }        for ( int d = 2; d < array_size; d++ )  // Display     {         if ( num[ d ] == true )         {             cout << setw( 5 ) << d;                         if ( counter &#37; 10 == 1 )                 cout << endl << endl;                         counter++;         }     }     cin.get();     return 0; }```
anon i'm not sure what your saying
Edit: no second condition
• 05-28-2007
anon
Code:

```    for ( int b = 2; b < (array_size / 2) + 1; b++ )  // Multiply all numbers from 2 to half array size     {         if ( num[ b ] == true /*|| b == 2*/) //why second condition??         {             for ( int c = b*b; c < array_size; c += b )  // Eliminate multiples             {                 num[ c ] = false;             }         }     }```
What happens in your code is that when you get to 2, you first mark b == c == 2 as non-prime, although the first non-prime to sieve out is 2*2 == 4. Similarly, when you get to 3, you mark it as non-prime, although the first non-prime to sieve out, again, is 3*3 == 9 (because you have already sieved out 6 == 2*3), etc.

It displayed anything at all because of the loop condition of the outer loop, meaning, the destruction would last only for the first half of the array...
• 05-28-2007
EdSquareCat
Oh I get it now! Thanks for not giving up on me :) Hmm that b * b was a good idea, although I'm not exactly sure why it never skips a number.

Code:

```#include <iostream> using std::cout; using std::cin; using std::endl; #include <iomanip> using std::setw; int main() {     const int array_size = 1000;     bool num[ array_size ];     int counter = 2;     for ( int a = 2; a < array_size; a++ )  // Set all elements to 1     {         num[ a ] = true;     }     for ( int b = 2; b < (array_size / 2) ; b++ )  // Multiply all numbers from 2 to half array size     {         if ( num[ b ] == true )         {             for ( int c = b + b; c < array_size; c += b )  // Eliminate multiples             {                 num[ c ] = false;             }         }     }        num[ 2 ] = true;     for ( int d = 2; d < array_size; d++ )  // Display     {         if ( num[ d ] == true )         {             cout << setw( 5 ) << d;                         if ( counter % 10 == 1 )                 cout << endl << endl;                         counter++;         }     }     cin.get();     return 0; }```
And by setting counter to 2, how come I still get 10 in each row? AGH!
• 05-29-2007
EdSquareCat
Also, if I wanted to increase the number to a very high one, how would I get it to display all the numbers, instead of only the last few?