Prime Numbers

This is a discussion on Prime Numbers within the C++ Programming forums, part of the General Programming Boards category; Prime Numbers 2 - 1000 Code: #include <iostream> using std::cout; using std::cin; using std::endl; int main() { int array_size = ...

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    13

    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.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    May 2007
    Posts
    13
    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
    Last edited by EdSquareCat; 05-28-2007 at 01:01 AM.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    > why are the first 2 numbers alone?
    Either the start value for counter is wrong, or you're testing the wrong result.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Should be
    Code:
      const int array_size = 1000;
    as standard C++ doesn't allow variable-length arrays.

  7. #7
    Registered User
    Join Date
    May 2007
    Posts
    13
    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
    Last edited by EdSquareCat; 05-28-2007 at 11:50 AM.

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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...
    Last edited by anon; 05-28-2007 at 11:50 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #9
    Registered User
    Join Date
    May 2007
    Posts
    13
    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!

  10. #10
    Registered User
    Join Date
    May 2007
    Posts
    13
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Replies: 18
    Last Post: 11-04-2005, 01:41 PM
  3. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 03:32 PM
  4. Prime numbers
    By Lazy Student in forum C Programming
    Replies: 12
    Last Post: 05-14-2002, 05:53 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 04:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21