Thread: Jumping into C++ Chapter 5 problem 6 - Critique please

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    16

    Jumping into C++ Chapter 5 problem 6 - Critique please

    I have been working through Jumping into C++ and in Chapter 5 one of the problems was to write a program that computes the first 100 prime numbers. With everything we have learned in the book this was not possible.

    I emailed Alex and he gave me a clue in the formula lhs - (lhs / rhs) * rhs. This would make is a "fakeModulus". I used this and only have one problem. It does not work on the number 2. Other than that it compiles and works perfect.

    Does anyone have an idea on this or is it just an imperfect formula for the number 2?

    Please critique my code and let me know if I could improve it. The deal is I could only use loops as this is all we have been taught in the book. Also, I could not use the sqrt function so on the prime numbers I looped it that many times. Example: 541 looped 539 times as I did not check for 1 or 541.

    Thanks,

    Mike

    Code:
    #include <iostream>
    
    // Write a program that computes the first 100 prime numbers.
    // Do this while only using loops.
    
    using namespace std;
    
    int main()
    {
        int prime_qty = 0;
        int prime_check = 0;
    
        cout << "How many prime numbers do you need? ";
        cin >> prime_qty;
    
        for ( int i = 1; i < prime_qty + 1; i++)
        {
            for ( int j = 2; j < i; j++)
            {
                prime_check = i - ( i / j ) * j;
                if (prime_check == 0)
                {
                    break;
                }
            }
            if ( prime_check != 0)
            {
                cout << i << "\n";
            }
            else
            {
                prime_qty++;
            }
        }
    }

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I don't see how it won't work with 2.

    If you can't use sqrt, you could use j * j <= i

    To speed up the algorithm twofold, you could check 2 separately before the outer loop and then make the inner loop start at 3 and increase by 2.

    Instead of this i < prime_qty + 1
    use this i <= prime_qty

    Why bother checking prime_check outside the loop? Why not just cout the number before the break?

    Why are you incrementing prime_qty???
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Now that I take another look at it, you're not controlling the outer loop properly. It needs to count how many primes you've found so far. It shouldn't be providing the number to test for primality. You need another number (not a loop) for that, and you may as well start that at 3 and go up by 2 as well, cout'ing 2 as a special case before the outer loop.

  4. #4
    Registered User
    Join Date
    Mar 2012
    Posts
    16
    The problem with 2 is: 2 - ( 2 / 2 ) * 2 = 0. If a return of 0 comes back it says the number is not prime. If I look at 8 when checking with 2: 8 - ( 8 / 2) * 2 = 0. The return of 0 at anytime means the number is not prime.

    I like the j * j <= i. I will work on that.

    I tried very hard to put an outer loop for a count of prime numbers that would count down when a prime number was found. I could not get it to work. So I decided to say if a number was not prime add one back on to my loop.

  5. #5
    Registered User
    Join Date
    Mar 2012
    Posts
    16
    Alex pointed out that my int prime_check = 0; was wrong. I changed it to 1 and 1 & 2 showed up. I fixed the prime_qty + 1 to be <=. I should have thought of that.

    I still do not know how to make the outer loop. I spent a couple of hours working on it and could not get it to work.

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    1 is not a prime number. They start at 2.

    Since this does not appear to be homework and it would take longer to talk you through it, here's an example solution. Also, used the modulus operator since it seems kind of stupid not to. (Look ahead in your book to see how it works!)

    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    {
        int prime_qty = 0;
    
        cout << "How many prime numbers do you need? ";
        cin >> prime_qty;
    
        // Treat 2 as a special case    
        if ( prime_qty > 0 )
            cout << 2 << "\n";
    
        int primes_found = 1;
        for ( int to_test = 3; primes_found < prime_qty; to_test += 2 )
        {
            int prime_check = 1;
            for ( int j = 3; j * j <= to_test; j += 2 )
            {
                prime_check = to_test % j;
                if ( prime_check == 0 )
                    break;
            }
            if ( prime_check != 0 )
            {
                ++primes_found;
                cout << to_test << "\n";
            }
        }
    }

  7. #7
    Registered User
    Join Date
    Mar 2012
    Posts
    16
    I have made corrections and now it looks like this. I didn't want 1 to be in there so started i at 2 and added +1 back to prime_qty.

    I would like to know how to put a working counter when it finds a prime number and have this run until the counter equals their request for the amount of prime numbers. I am sure that the counter++ would go under the cout << i << "\n";. I just do not know where to put the start of the loop.

    Updated code:
    Code:
    #include <iostream>
    
    // Write a program that computes the first 100 prime numbers.
    // Do this while only using loops.
    
    using namespace std;
    
    int main()
    {
        int prime_qty = 0;
        int prime_check = 1;
    
        cout << "How many prime numbers do you need? ";
        cin >> prime_qty;
    
        for ( int i = 2; i <= prime_qty + 1; i++)
        {
            for ( int j = 2; j * j <= i; j++)
            {
                prime_check = i - ( i / j ) * j;
                if (prime_check == 0)
                {
                    prime_qty++;
                    break;
                }
            }
            if ( prime_check != 0)
            {
                cout << i << "\n";
            }
        }
    }

  8. #8
    Registered User
    Join Date
    Mar 2012
    Posts
    16
    Thanks oogabooga. You posted this while I was typing up my post. I will read through your code.

    You are right this is not homework. I wanted to learn C++ so I was surfing the net and found this site. I saw the recommended book list and bought the #1 book Jumping into C++ and started doing it from page 1. I don't have anyone to look at my work so I was posting it here.

    Thanks,

    Mike

  9. #9
    Registered User
    Join Date
    Mar 2012
    Posts
    16
    I realize what I was doing wrong with my primes_found. I was trying to create a while loop until primes_found was = to primes_qty. All I had to do was replace i <= prime_qty with primes_found < primes_qty. Thank you so much. I was trying to make it so much harder than it was. In the next two chapters I will make update this with new things such as functions.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. K & R Chapter 1.9 getline problem
    By kkk in forum C Programming
    Replies: 11
    Last Post: 08-31-2011, 11:57 PM
  2. Jumping to OOP in C++ from C
    By meadhikari in forum C++ Programming
    Replies: 6
    Last Post: 07-16-2010, 05:26 AM
  3. debug problem --> chapter 5.6 K&R
    By c_lady in forum C Programming
    Replies: 2
    Last Post: 06-18-2010, 03:26 AM
  4. problem with quix chapter 4
    By roelof in forum C++ Programming
    Replies: 2
    Last Post: 05-31-2010, 08:38 AM
  5. Jumping between functions
    By Nexus-ZERO in forum C Programming
    Replies: 8
    Last Post: 01-14-2008, 03:47 AM