# Prime factor tree

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.

I'm pretty satisfied with what I did, but I want a review. Can I make it better? If I have a lot to improve on, examples would be great.

#include <iostream>
#include <string>

//function prototype
int PrimeFactor(int number);
bool isPrime(int PrimeOrNot);

int main() {
int i;
int PrintThePrime=0;

//here we take the numbers from 2-1000 instead of 0-1000 because 0 is not normal number and not a prime number and number one is both so we considor it like none and just gonna ignore this two folks
for (i = 2; i < 1000; i++) {
if (isPrime(i)) { //check if the number already a prime , cause if he is we do not need waist performance and run the all function =)
std::cout << "Already a Prime :" << i << std::endl;
}

//here is begin the fun =)
else {
PrintThePrime = PrimeFactor(i); //function that perform some things and return THE SUM FACTORS OF THE NUMBER.

//check if the return number is a prime.
if (isPrime(PrintThePrime)){
std::cout << i << ": "; //print the original number before the performance of prime tree.
std::cout << PrintThePrime << std::endl; //the actuall Factor sum of the original number.
}
}

}
return 0;
}

int PrimeFactor(int number)
{
int i;
int SecondHalf;
int sum = 0;

for (i = 2; i < number; i++) // the divider of the loop
{
if (i == 4 || i == 8 || i == 6){ //purpose if the number not divisible by 2 and 3 there is no purpose to check if they divisible by 4|6|8 and that because every number from here is divisible by 2 or 3.
continue;    //another note take a look and see that divide by 9 is either not needble cause every number that divides by 9 divides by 3
}               //but he is not here cause the loop never gonna reach the number 9 , numbers 4|8|6 can be reachable if the original number is not divisible by 2|3 but divisble by 5|7.

if (number % i == 0) { //just check what ever divider is gonna be used
number = number / i; //first half of the number
SecondHalf = number*i / number; //second half of the number

if (isPrime(number)) //check if the first half of the number is now a prime
sum = sum + number;
else //if the first half is not an prime the divider of teh loop gonna be reset and the loop start again but now from the loop prespective the origin number is the first_half
i = 1; //that gonna be divided to two halfs.

sum = sum + SecondHalf; //second half gonna be always putted into the sum and that cause it the divider and the dividers that used in this loop is only primes =)
}
}
return sum; //and here fun is comming to end , but wait there is a bit more =)
}

//function that called a lot and check if the number is prime.
bool isPrime(int PrimeOrNot)
{
int i;

for (i = 2; i < PrimeOrNot; i++) //take a number and divide him from 2 to it self-1 , and that cause prime can be divided only by 1 and itself.
{
if (PrimeOrNot % i == 0) //if the number that divided is dividable by on of the loop number , he is not a prime and at that point the loop can finish.
return false; //the indicator of that , that the number is not a prime.
}
return true; //if the number is goin through the all loop and not dividable by anyone of the number he is a prime , take a look and see something tricky a bit the number 2 is gonna be a prime
//just because he is not answer to the loop condition , but it alright he is really a prime.
}


## 2 Answers

• You're using both camelCase and PascalCase inconsistently for variables and functions. Choose one and stick with it.

• You can declare loop counter variables in C++, so there's no need to do so outside of loops.

• You don't need your own return 0 at the end of main(). It will provide this return for you.

• The variable PrintThePrime sounds more like a function name (and is a verb). Rename this so that it makes more sense in this program, and make it a noun.

• The parameter PrimeOrNot sounds like it's a bool, yet it's being used differently in the loop. This should also be renamed for clarity.

# Comments are distracting

The number of comments in the code is too much and distracts from reading the code. I would prefer one large comment before each function explaining things rather than one comment per line.

# Inefficiencies

There are some places in the code that are inefficient:

1. When you find a prime factor, you set i = 1. You don't need to do that because you won't find any more prime factors less than i. What you do need to do is keep retrying i because the same prime factor can divide multiple times into your number.

2. After each division, you check if the remaining number is a prime. I'm not sure if that makes things faster or slower, but if number is prime, you should return immediately instead of continuing in the loop, because there will be no more divisors.

# Faster method

A faster way of doing this would be to precompute the primes from 1..N using something like a Sieve of Eratosthenes algorithm. That way, your isPrime() function becomes an array lookup instead of a loop. Also, if you generate a list of primes from the Sieve, your main factoring loop will be much faster because you can only divide by primes instead of dividing by every number.

I wrote a program using this method and it was 50x faster than your program when computing up to 100000, and 600x faster than your program when computing up to 1000000 (0.60 seconds vs 365 seconds).

• well first off all thank you all for comment and review , just want to give a point about (note 1 . i=1 . i do need that you take a case when it prime what if the number was not a prime , in that case i should start the loop from scratch and devide the new number into two , to continue the prime factor tree. – netboyo delo Oct 25 '15 at 5:28
• @netboyodelo Either i-- will suffice where you have i=1, or you could make a nested loop to keep dividing by i, and then you can move on to i+1 in the next iteration. You don't have to restart all the way from 1. – JS1 Oct 25 '15 at 5:53
• well i-- is not the way , what if the number is divided by 5 and then the new number is devided by 2 but i will divide him by 4 in your senario and then i will go into trouble cause dividing number by 4 is not really possible in my program. nested loop i will need to give it a shot. – netboyo delo Oct 25 '15 at 6:00
• @netboyodelo Give me a real example where you can divide by 5 and later need to divide by 2? It's not possible because you already divided by 2 before you got to 5. Also, i-- does not make i go to 4. It makes i remain at 5 because there will be a i++ right after. – JS1 Oct 25 '15 at 6:08
• there is no case when the original number can be divided first only by 5 and then the factor can be divided by 3? – netboyo delo Oct 25 '15 at 6:15