C++ Prime factor program 2 problems.

Question

Okay so I"m writing a program (in C++) that is supposed to take a number, go through it, find out if it's factors are prime, if so add that to a sum, and then output the sum of all of the imputed number's prime factors.

My program successfully seems to do this however it has 2 problems,

1) The number I am supposed to test to see the sum of the prime factors of this number (600851475143) but it's too big for an int. I'm not sure what other variable type to use, or which variable's types to change. I would really like a clear explanation on this if at all possible.

2) For some reason, when the program checks to see if 1 is a factor of the number, and then checks to see if 1 is prime, it says 1 is prime, even though the first step of the function for checking to see if it's prime is that if it's 1 then it isn't prime. I found a fix for this, by telling it to subtract 1 from the very last value for the sum of all prime factors. However, this is a fix, not really finding the problem. If someone could point out at least where the problem is I would appreciate it!

Here's the code, if you have questions, please ask!

#include <iostream>

using namespace std;

bool prime (int recievedvalue) { //starts a function that returns a boolean with parameters being a factor from a number
     int j =1;
    int remainderprime = 0;
    bool ended = false;
    while (ended == false){ //runs loop while primality is undetermined
        if (recievedvalue == 1){ //if the recieved value is a 1 it isn't prime
            //not prime
            break; // breaks loop
            return false;
            }
        remainderprime=recievedvalue%j; //gives a remainder for testing
        if ((remainderprime==0 && j>2) && (j!=recievedvalue || j == 4)){ //shows under which conditions it isn't prime
        ended=true;
        //not prime
        return false;
        }
        else if (j==1){
            j++;
            }
        else if ( recievedvalue==2 || j==recievedvalue ){ // shows what conditions it is prime
          ended = true;
          //prime
          return true;
            }
            else {
            j++;
                }
        }
    }


int multiple(int tbfactor){ //factors and then checks to see if factors are prime, then adds all prime factors together
    //parameter is number to be factored
    int sum = 0;
    bool primetest = false;
    int remainderfact;
    int i=1;
    while (i<=tbfactor){ //checks if a i is a factor of tbfactor
        remainderfact=tbfactor%i;
        if (remainderfact==0){ //if it is a factor it checks if it is a prime
            primetest = prime(i);
        }
            if (primetest ==true){ //if it is prime it add that to the sum
                sum += i;
                primetest=false;
                }
                i++;
            }
            sum --; // for some reason it always ads 1 as a prime number so this is my fix for it
            return sum;
    }

int main()
{

    int input;
    int output;
    cout << "Enter number to find the sum of all it's prime factors: ";
    cin >> input;
        output = multiple(input);
    cout << output;
    return 0;
}

I'm really new to this, like a few days or so, so I'm very unfamiliar with stuff right now so please explain easily for me! I look forward to your help! Thanks!

Answer 1

1. Use either a 64 bits number on a 64 bits system, or use a library that does arbitrary precision arithmetic
2. Remove the break before the return false. Because of the break, execution is resumed outside the loop and return false is never executed.

Answer 2

For 1), you need to use a larger datatype. A 64-bit integer should be enough here, so change your ints to whatever the 64-bit integer type is called on your platform (probably long, or maybe long long).

For 2), the problem appears to be that you have a break before your return false. The break causes the code to stop the while loop immediately and continues execution immediately after the loop. It doesn't appear that the return value is ever assigned in that case (which your compiler should be warning you about), so the actual value returned is effectively arbitrary.

Answer 3

To store values larger than 4 bytes (the capacity of an int) you have a variety of options. Refer to this page for those options. As to why you're program is returning true for the check on whether or not 1 is prime, check out this section of code:

if (recievedvalue == 1){ //if the recieved value is a 1 it isn't prime
   //not prime
   break; // breaks loop
   return false;
}

The break statement will exit and return false will never be reached. To solve the problem, remove the break statement.

Answer 4

While others have pointed out a problem with your data types, there's a few problems with the structure of the first function that immediately caught my eye. (BTW, your indentation is enraging.) Look at this stripped-down version:

bool prime (int recievedvalue) {
    // ...
    bool ended = false;
    while (ended == false){
        if (...){
            break; // jumps _behind_ the loop
            return false;
        }
        // ...
        if (...) {
            ended=true;
            return false; // leaves function returning true
        }
        else if (...) {
            // ...
        }
        else if (...) {
          ended = true;
          return true; // leaves function returning false
        }
        else {
            // ...
        }
    }
    // behind the loop

    // leaves function returning random value
}

For one, every time you set the loop control variable ended, you leave the loop anyway using some other means, so this variable isn't needed. A while(true) or for(;;) would suffice.

Also, that break jumps behind the loop's body, but there isn't a statement there, so the code leaves the function without explicitly returning anything! That's invoking so-called Undefined Behavior. (According to the C++ standard, your program is, from this point on, free to do whatever it pleases, including returning random values (most implementations will do that), formatting your HD, invoking nasty Nasal Demons on you, or returning exactly what you expected, but only on Sundays.)

Finally, that break occurs right before a return false; which is therefor never reached. Actually your compiler should warn about that. If it doesn't, you're likely not compiling at the highest warning level. (You should turn this on. Always try to cleanly compile your code at the highest warning level.) If it does, learn to pay attention to compiler warnings. They are a very important tool for diagnosing problems during compilation. (Remember: Errors diagnosed during compilation need no testing and never make it to the customer.)