Program won't run with really big numbers

Question

Hi there, I'm pretty new to programming and so I"m making this program in C++ that will take a number and find it's prime factors, which works great! Unless it's too big for an int variable. Now then I tried to change all of the int variables to long long variables so it wouldn't matter, but this doesn't seem to fix the problem. The program is as follows:

#include <iostream>

using namespace std;

bool prime (long long recievedvalue) { //starts a function that returns a boolean with parameters being a factor from a number
    long long j =1;
    long long 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
            return false;
            break; // breaks loop
            }
        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++;
            }
        }
    }


long long multiple(long long tbfactor){ //factors and then checks to see if factors are prime, then adds all prime factors together
    //parameter is number to be factored
    long long sum = 0;
    bool primetest = false;
    long long remainderfact;
    long long 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++;
    }
    return sum;
}

int main()
{
    long long input;
    long long output;
    cout << "Enter a number > 0 to find the sum of all it's prime factors: ";
    cin >> input;
    if (input == 0 || input <= 0){
        cout << "The number you entered was too small."<< endl << "Enter number a number to find the sum of all it's prime factors: ";
    cin >> input;
        }
    output = multiple(input);
    cout << output << endl << "finished";
    return 0;
}

Now then to be sure, the problem does the same thing whether or not it's a int or not. Also like I said I"m new to programming, and C for that matter so I look forward to your easily understandable replies. :)

Answer 1

I'm willing to be that your program IS running. I'm sure that someone is going to pop on and give you the answer in a heartbeat, but I'm hoping that it doesn't happen so that you get to experience the same thing that I did when I ran into the problem YEARS ago.

Do this: start with 1, and work up from there using powers of 2 (1, 2, 4, 8, 16, etc.) and just keep going, doubling the input number each time. When does it "stop running?" Does it get progressively slower?

Please comment back on my post or on your own, or edit your own, or post an answer, whatever it is you're allowed to do with only 56 rep. If the community will allow it (and of course I would like the community to further the lesson), I'd like to gently push you to the answer through a series of back-and-forth steps feedback rather than the typical fashion, since this is an obvious unique learning opportunity.

Answer 2

If you are trying to find if a number is a prime or not, here is a fast solution,

#include <iostream>

using namespace std;

#define ullong unsigned long long

bool prime (ullong x)
{
    if(x <= 1)
        return false;

    ullong s = (ullong)sqrt(x);

    for(ullong i=2;i<=s;i++)
        if(x%i == 0)
            return false;

    return true;
}