C factoring a number into prime factors

Question

I wrote a program that factors numbers into its prime factors, then stores them in a vector, and lastly asks whether to verify the result by multiplying them out.

It works this way: ask for a number (num in the code), and divide it by 2 and up.

If it finds a number (the divisor in the code) whose modulo (when num mod divisor) is zero, store that divisor into a vector, and reduce num by dividing it by the divisor and store it into temp, and reset the divisor to 1 (and the last statement in the while loop will increment it to 2. If no such number is found, divisor increases until it is greater or equal to num. This process continues until divisor is greater than num.

Here is the code:

#include <iostream>
#include <vector>

using namespace std;

int main() {

    //num=the number of interest
    //divisor=the number dividing the number of interest each time
    unsigned long  divisor=2, num, temp ; //num=13699293826d
    char c;

    vector<unsigned long> divisors;
    cout<<"Enter a number: "<<endl;
    cin>>num;

    //temp stores the number that is reduced each time
    temp=num;

    while(divisor<=num)
    {
        if(temp%divisor==0)
        {
             temp=temp/divisor;
             divisors.push_back(divisor);
             cout<<"one "<<divisor<<endl;
             cout<<"the number of interest is now"<<temp<<endl;
             divisor=1;
        }
        if(divisor==temp&&temp!=1)
        {
            cout<<"two " << divisor<<endl;
            divisors.push_back(divisor);
        }

        divisor++;
    }

    if(divisors[0]==num)
    {
        cout<<"The number: "<<num<<" is prime. ";
    }
    else
    {
        cout<<"Its proper divisors are: ";
        for(unsigned int count=0; count<divisors.size(); count++ )
        {
            cout<<divisors[count]<<"\t";
        }
    }

    cout<<"Print out the multiplication? Press 'Y' or 'N'."<<endl;
    cin>>c;

    if(c=='Y'||c=='y')
    {
        for(unsigned int count=0; count<divisors.size(); count++)
        {
            temp*=divisors[count];
            cout<<temp<<"\t";
        }
    }
    return 0;
}

I have printed some debug cout statements.

The problem I have with it is this: when the number is sufficiently large, the debug statement "the number of interest is now", has the number 1 following it. Then, the program crashes.

What is wrong with the code?

Thanks.

---

And yes, I am running it on 64 bits.

A sample program output:

    Enter a number: 
    13699293826
    one 3
    the number of interest is now: 1431655765
    one 5
    the number of interest is now: 286331153
    one 17
    the number of interest is now: 16843009
    one 257
    the number of interest is now: 65537
    one 65537
    the number of interest is now: 1

And then the program crashes.

I also noticed that the first "prime factor" of 3 is incorrect, because 13699293826 divided by 3 is 4562761275.333333333333333.....

edit # 2------------------------------------------

    temp 65537, divisor 62287

    ..............omitted output

    temp 65537, divisor 65530
    temp 65537, divisor 65531
    temp 65537, divisor 65532
    temp 65537, divisor 65533
    temp 65537, divisor 65534
    temp 65537, divisor 65535
    temp 65537, divisor 65536
    temp 65537, divisor 65537
    one 65537
    the number of interest is now: 1
    Its proper divisors are: 3  5   17  257 65537   Print out the                 multiplication? Press 'Y' or 'N'.

And then the program stops responding, and it does not work when I press "y" and enter.

Also, the number multiplied are not correct; the result is 4294967295... after googling, it says it is "the highest number you can get using 32 bits (BInary digiTS)". But on my PC, it says the operating system is 64 bit.

Answer 1

When you get the message "the number of interest is now 1" it means that temp == 1 now. You should have stopped at this point but you continue, because your loop erroneously compares divisor with num, whereas it should be comparing it with temp.

So now temp == 1 and divisor == 2, and you will loop until the unsigned long divisor wraps around to 0. At which point your check if(temp%divisor==0) causes division by zero. I'd expect this to happen for any input.

---

You shouldn't reset the divisor, and your loop condition is wrong. Your loop should be like this:

while( divisor*divisor <= temp)
{
    if(temp%divisor==0)
    {
         temp=temp/divisor;
         divisors.push_back(divisor);
         cout<<"one "<<divisor<<endl;
         cout<<"the number of interest is now"<<temp<<endl;
         ///// divisor=1;
    }
    /* ------ if(divisor==temp&&temp!=1)
    {
        cout<<"two " << divisor<<endl;
        divisors.push_back(divisor);
    } ------- */
    else ////////
        divisor++;
}
if( temp > 1)
{
    divisors.push_back( temp );
    temp = 1;  // <<-------------- ADD THIS
}