prime numbers problem

[Fauch911]

Hi,

I've been given this task:

Design a program tat finds all numbers from 1 to 100 whose prime factors, when added together, sum up to a prime number.

I have written this code

#include <iostream>

using namespace std;

bool isPrime (int sum);
bool isDivisible (int sum, int divisor);
int primefactors_search (int number);

int main()
{
    //Variables
    int primsum;
    //main loop checks if the sum of the uime factors is a prime number
    for (int i = 1; i < 100; i++)
        {
        primsum = (primefactors_search(i));
        if (isPrime(primsum) == true)
        {
            cout << i << endl;
        }

        }

}

bool isPrime (int sum)
//Function checking for prime numbers
{

for (int i = 2; i < sum; i++)
    {
        if (isDivisible ( sum, i ) )
        {
            return false;
        }
    }
return true;
}

bool isDivisible (int sum, int divisor)
//Subfunction of isPrime
{
    return sum % divisor == 0 ;
}

int primefactors_search (int number)
//find prime factors and add them up
{
int a=0;
    {
        for (int i = 1; i <= number; i++)
            {
            if (isPrime(i)== true)
                {
                if ((number%i) == 0)
                    {
                    a= a+i;
                    return a;
                    }
                }
            }
    }
}

However the program doesnt do what it should...
Can you help me and show me where i went wrong?
Any help will be much appreciated.

[abhishekm71]

the only error i could spot is that in the last function, the 'return a' should be at the end of the program and not within the if braces.

Also, according to your program '1' will be a prime number whereas mostly it is neither a prime nor a composite.

[becomingEng]

THe last function should goes like this :

int primefactors_search (int number)
//find prime factors and add them up
{
int a=0;

        for (int i = 1; i <= number; i++)

            if (isPrime(i)== true)
				if ((number%i) == 0)
                    a= a+i;
			return a;
	}

[Fauch911]

Problem is i'm getting wrong output. The program outputs 8, for example whose prime factors are 2,2 and 2, and sum up to 6, which is NOT a prime number.

I fixed the return a issue in the last paragraph.
Also "fixed" the (1) prime factor issue.

Could someone please compile this and show me what part is wrong?

Thank you in advance.

(edit: new version of code)

#include <iostream>

using namespace std;

bool isPrime (int sum);
bool isDivisible (int sum, int divisor);
int primefactors_search (int number);

int main()
{
    //Variables
    int primsum;
    //main loop checks if the sum of the uime factors is a prime number
    for (int i = 1; i < 100; i++)
        {
        primsum = (primefactors_search(i));
        if (isPrime(primsum) == true)
            {
            cout << i << endl;
            }

        }

}

bool isPrime (int sum)
//Function checking for prime numbers
{

for (int i = 2; i < sum; i++)
    {
        if (isDivisible ( sum, i ) )
        {
            return false;
        }
    }
return true;
}

bool isDivisible (int sum, int divisor)
//Subfunction of isPrime
{
    return sum % divisor == 0 ;
}

int primefactors_search (int number)
//find prime factors and add them up
{
int a=0;
for (int i = 2; i < number; i++)
    {
        if (isPrime(i)== true)
            {
            if ((number%i) == 0)
                {
                a= a+i;
                }
            }
    }
return a;
}

[abhishekm71]

the problem is that you are checking each prime factor only once. for instance if the number is 8, then the sum (a) will 2 and not 2+2+2. Since 2 is prime, the program will output 8. Hope I am clear.

[Fauch911]

yeah i got it. trying to fix now, thanks a lot.

[Fauch911]

still having problems with this.

in theory it should be easy since my last function returns a prime factor, so i could just use this function on my number over and over until isPrime(i) becomes true. however it seems i am too dumb to write the proper code for it.

could someone help again please :o

thanks in advance

[abhishekm71]

You need to modify your function primefactors_search. instead of:

int primefactors_search (int number)
//find prime factors and add them up
{
int a=0;
for (int i = 2; i < number; i++) 
    {
        if (isPrime(i)== true)
            {
            if ((number%i) == 0)
                {
                a= a+i;
                }
            }
    }
return a;
}

try something like the following. (please note this code is just to give you a direction and it may contain lots of bugs)

int primefactors_search (int number)
//find prime factors and add them up
{
int a=0;
while (number != 1)
    {
        int found = 0;
        for (int i=2;i<=number && !found;i++)
        if (isPrime(i)== true)
            {
            if ((number%i) == 0)
                {
                a= a+i;
                found = 1;
                number /= i;
                }
            }
    }
return a;
}

[Fauch911]

thanks a lot, your code actually gives the correct results.

questions:

now i need to figure out what your code actually does, and why i didnt come up with that =]

[abhishekm71]

my code simply does the following:
1. finds a prime factor of the number "N".
2. adds it to the sum. divides N by that prime factor (so that it doesnt get repeated in the next iteration).
3. repeats the steps 1 & 2 till N = 1.