Thread: Prime Numbers

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.

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

> why are the first 2 numbers alone?
Either the start value for counter is wrong, or you're testing the wrong result.

The formating looks like this, because the first time you print the newline, counter is 1 (1%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.

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

What I meant to say was this:

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...