Thread: Prime Factors

  1. #1
    Registered User
    Join Date
    Jun 2012
    Posts
    8

    Prime Factors

    Exercise: Design a program that finds all numbers from 1 to 1000 whose prime factors, when added together, sum up to a prime number (for example, 12 has prime factors of 2, 2, and 3, which sum to 7, which is prime).

    I did that, but it is not working:

    Code:
    #include <iostream>
    
    using namespace std;
    
    int sum = 0;
    
    bool prime (int number);
    bool primeSum (int number);
    
    int main()
    {
        for (int i = 2; i <= 1000; i++)
        {
            if (prime(i))
            {
                if (primeSum(i))
                {
                    cout << i << endl;
                }
                sum = 0;
            }
        }
        cin.get();
        return 0;
    }
    
    bool prime (int number)
    {
        for (int i = 2; i < number; i++)
        {
            if (number % i == 0)
            {
                return false;
            }
        }
        return true;
    }
    
    bool primeSum (int number)
    {
        for (int i = 2; i <= number;)
        {
            if (number % i == 0)
            {
                sum += i;
                number /= i;
                i--;
            }
        }
        if (prime(sum))
        {
            return true;
        }
        return false;
    }

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    function prime will not allow e.g. number 12 to proceed to next calculations(line 14)

  3. #3
    Registered User
    Join Date
    Jun 2012
    Posts
    8
    Quote Originally Posted by std10093 View Post
    function prime will not allow e.g. number 12 to proceed to next calculations(line 14)
    why not? can you explain?

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    The biggest error is testing for primality in main, which only passes prime numbers on for testing, which is pointless (they all pass since their prime factor -- themselves -- is prime). Either remove that test, or perhaps negate it, only passing on composite numbers since the primes are kind of boring in this context.

    Another bad error is that you don't increment the loop variable in primeSum.

    An element of bad programming style is defining sum as a global. Just put it in primeSum and init it to zero.

    Voila:
    Code:
    #include <iostream> 
    using namespace std; 
    
    bool prime (int number); 
    bool primeSum (int number); 
    
    int main() 
    {
        for (int i = 2; i <= 1000; i++) 
        { 
            if (!prime(i) && primeSum(i)) // remove !prime(i) to test all numbers
            { 
                cout << i << endl; 
            } 
        } 
        cin.get(); 
        return 0; 
    } 
    
    bool prime (int number) 
    { 
        for (int i = 2; i < number; i++) 
        { 
            if (number % i == 0) 
            { 
                return false; 
            } 
        } 
        return true; 
    } 
    
    bool primeSum (int number) 
    { 
        int sum = 0;
        for (int i = 2; i <= number;) 
        { 
            if (number % i == 0)
            { 
                sum += i; 
                number /= i; 
                continue; // test same factor again
            } 
            i++;
        } 
        return prime(sum); 
    }
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  5. #5
    Registered User
    Join Date
    Jun 2012
    Posts
    8
    Hm... I started to learn a few days ago... I'm getting better
    But... explain me one thing. If the variable 'i' in a for loop is equal, for example, 10, and I put a continue keyword, it returns to 10 or it goes to 11?

    *Line 41 you put*

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by mgcpovoleri View Post
    If the variable 'i' in a for loop is equal, for example, 10, and I put a continue keyword, it returns to 10 or it goes to 11?
    It stays at 10. It only gets incremented if the increment statement (i++) is executed. The continue statement says to go to the test part of the loop and since your loop update (the 3rd "parameter" to for) is empty, 'i' is not modified.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  7. #7
    Registered User
    Join Date
    Jun 2012
    Posts
    8
    Quote Originally Posted by oogabooga View Post
    It stays at 10. It only gets incremented if the increment statement (i++) is executed. The continue statement says to go to the test part of the loop and since your loop update (the 3rd "parameter" to for) is empty, 'i' is not modified.
    Oh... sorry. Stupid question :x

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 02-19-2009, 10:32 PM
  2. Prime Factors
    By Adrian in forum C++ Programming
    Replies: 3
    Last Post: 10-02-2007, 09:01 PM
  3. Replies: 3
    Last Post: 03-29-2005, 04:24 PM
  4. Finding prime factors
    By ripper079 in forum C Programming
    Replies: 3
    Last Post: 05-17-2002, 09:23 PM