"Jumping Into C++".Practice problem.Chapter 7_3

[Icyblizz]

I am reopening this topic because the solution to this problem is not complete.
When you try to test the related topic code samples you will notice that the program outputs numbers like

14,20,...

and so on which are not part of the solution,I'm talking about the edited code sample here,not the original one.

Problem:

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). Implement the code for that algorithm.

Complete Solution:

#include <iostream>
#include <math.h>

using namespace std;

bool isDivisible(int number,int divisor);
bool isPrime(int number);
int sumFactors(int number);

int main(int argc,char* argv[])
{
    for(int i=2;i<=1000;i++)
    {
        if(isPrime(sumFactors(i)))
            cout<<i<<"\t";
    }
    cout<<endl;
}

int sumFactors(int number)
{
    int sum=0;
    if(isPrime(number))
        return sum;
    int aux=number;
    for(int i=2;i<aux;i++)
        {
            while(isDivisible(number,i))
            {
                number/=i;
                sum+=i;
            }
        }
        return sum;
}

bool isPrime(int number)
{
    for(int i=2;i<=sqrt(number);i++)
    {
        if(isDivisible(number,i))
            return false;
    }
    return true;
}

bool isDivisible(int number,int divisor)
{
    return number%divisor==0;
}

Just setting the record straight.Hope it helps some people.

[lastchance]

Just as a matter of interest, why aren't the prime numbers themselves part of your output?

Take 13, for example.
Its only prime factor ... is 13 ... which when summed ... gives 13 ... which is prime .... so ought to be in your list.

Try this instead. The output is the same as yours except that it includes the prime numbers as well - which seems more consistent with your statement of the problem (I don't have the book).

#include <iostream>
#include <cmath>
using namespace std;

//----------------------------------------------------------------------

int smallestFactor( int N )
{
   int maxTest = sqrt( N );
   for( int test = 2; test <= maxTest; test++ )
   {
      if ( N % test == 0 ) return test;
   }
   return N;      // default (no non-trivial factors, or cases N <= 1)
}

//----------------------------------------------------------------------

int main()
{
   const int MAX = 1000;
   int ntest, n, sum, p;

   for ( ntest = 2; ntest <= MAX; ntest++ )
   {
      n = ntest;
      sum = 0;
      while ( n != 1 )
      {
         p = smallestFactor( n );   n /= p;
         sum += p;
      }
      if ( smallestFactor( sum ) == sum ) cout << ntest << '\t';
   }
}

If you prefer not to include the prime factors themselves, then change line 33 to
if ( smallestFactor( sum ) == sum && smallestFactor( ntest ) != ntest ) cout << ntest << '\t';
and you will get exactly the same output as your own.

[newbieg]

Entrant Disqualified.
--------------------------------

[I phrased the challenge poorly, I knew you were still not to vectors in the book. I was hoping to get someone else to play with it and try to optimize it even more.

my bad.]

[Icyblizz]

I have modified the code to include the prime numbers into the output.

@lastchance you are right about the regular prime numbers to be part of the solution.
Thank you for pointing this out,as to why I didn't include them from the start,I guess I just found them redundant while testing and forgot to put them back into the final output.

@newbieg your code works neat too,sadly this problem is in an early chapter in the book and vectors are not yet introduced.

P.S.
1. The only thing the book says about this problem is mentioned in the description,no other hints.
2. http://www.cplusplus.com/forum/beginner/107652/#msg584152 is the original post I was referring to,but I can't comment there and any sample you test is flawed somehow.

Thank you again for your correction!