working with extremely large numbers

[vince1981]

First time poster here. I took a c++ class in high school about 12 years ago, but haven't done any programming since. I'm trying to pick things up again, but I wasn't that good to begin with, and I've forgotten almost everything. So please be patient.

I'm working on a program that finds the prime factors of a given number and then outputs the largest of those factors. Because it finds the factors in ascending order, I'm considering just outputting the last value of int factor instead of using a separate variable (compare with factor, if factor is larger, set variable to value of factor), but that's a UI/design issue and not my current problem.

The code works perfectly unless the number I want to factor gets larger than about 2.14 billion.

The number I need to find the prime for is over 600 billion, so this is a problem.

I suspect this has something to do with variable types (obviously integers won't go that high), but switching the variable types isn't working.

I'd appreciate some help here. Here's my code:

#include<iostream>
#include<math.h>
using namespace std;

//Is factor prime?
bool checkprime(int a)
{   
    //0, 1, and negative numbers are not prime 
    if (a<2) return(false);
    
    //2 is a prime
    if (a==2) return(true);
    
    //any even number > 2 is divisible by 2 and is not prime
    if (a>2 && (a%2)==0) return(false);
    
    //no need to check multiples of 3
    if (a>3 && (a%3)==0) return (false);
    
    //no need to check multiples of 5
    if (a>5 && (a%5)==0) return (false);
    
    //no need to check multiples of 7
    if (a>7 && (a%7)==0) return (false);

    //no need to check multiples of 11
    if (a>11 && (a%11)==0) return (false);
    
    //no need to check multiples of 13
    if (a>13 && (a%13)==0) return (false);

    //no need to check multiples of 17
    if (a>17 && (a%17)==0) return (false);

    //no need to check multiples of 19
    if (a>19 && (a%19)==0) return (false);
    
    //number is not prime if evenly divisible by any number >=2
    for (int b=3; b<a; b++)
        {
             if (a%b==0) return(false);
        }
    
    //number is greater than 2 and not evenly divisble by any numbers except
    //1 and itself
    return(true);
}

int main()
{
	long input;        //We want to find the prime factors of this
	
	long working;      //Initializes to value of input (to preserve original
	                   //value of input for later use)
	                   
	long factor=2;      //The lowest possible prime factor
	
	int linebreak=0;   //Once I get this working, I'll use this to determine
	                   //whether to put a line break after outputting a factor
	
    char moveon='y';   //Determines whether the user wants to factor another
                       //number

    long lprime=0;      //The largest prime factor of input
    
    //Repeat this loop until the user enters something other than y or Y
	while (moveon=='y'||moveon=='Y')
	{
        //gets the number to work with from the user, initializes working 
        //to that same value
        cout<<"Please enter a positive integer."<<endl;
        cin>>input;
        working=input;
        cout<<endl<<endl;
        cout<<"The prime factors of "<<input<<" are:"<<endl;

		//factor was initialized at 2; this loop determines how many times (if
		//any) 2 factors into working
        while (factor==2)
		{
			while (working%factor==0)
			{
                if (linebreak<4)
                {
				    cout<<factor<<"     ";
                    working=working/factor;
				    linebreak++;
                }
                else
                {
                    cout<<factor<<"     "<<endl;
                    working=working/factor;
                    linebreak=0;
                }
			}
            
            //2 is currently the largest prime we've found
            lprime=factor;
			//Once working can't be divided by 2, we increment factor by 1 to
			//exit the while loop
			factor++;
		}

        //For a given number (working), any factor greater than or equal to the
        //square root of working (i.e., if factor*factor<=working)
        //cannot be prime, so for each iteration, we're testing a smaller 
        //set of numbers because working keeps shrinking as we remove factors 
		while (factor<=working)
		{
			//If it's not prime, it can't be a prime factor
            while (checkprime(factor))
			{			
				//If working/factor returns no remainder or if working equals
                //factor, factor is indeed a prime factor of our original 
                //number (input); Can I have multiple conditions for a while 
                //statement like this?
                while ((working%factor)==0&&working>1)
				{
                    if (linebreak<4)
                    {
                        cout<<factor<<"     ";
                        working=working/factor;
                        linebreak++;
                    }
                    
                    else
                    {
                        cout<<factor<<"     "<<endl;
                        working=working/factor;
                        linebreak=0;
                    }
                    
			     	if (factor>lprime) lprime=factor;
				}
				
				factor+=2;
			}

			factor+=2;
		}
        
        cout<<endl<<endl<<"The largest prime factor of "<<input<<" is "<<lprime<<"."<<endl;
        cout<<"Try another number (y/n)?"<<endl<<endl;

        //resets factor to 2 in case user wants to check another number
        factor=2;

		cin>>moveon;
	}

	return 0;
}

Also, I realize there's probably more efficient ways to do this. I welcome any advice on how to do so, but I'd also love to get it to work the way it is.

Thanks for your help.

-Vince

[m4ster r0shi]

The best thing you can do is use a big number library -> http://gmplib.org/

[vince1981]

The best thing you can do is use a big number library -> http://gmplib.org/

Sounded like an easy solution until I downloaded it. I'm using Dev-C++ on Windows 7. Any advice/instructions for adding this library? The instructions that come with it are obviously intended for people more familiar with this stuff than me.

[vince1981]

Using long long variables worked. I'm hoping I won't need to work with anything larger than 600 billion in the future.

[Duthomhas]

What compiler are you using?

You will have to compile the library (unless you are on a common platform where precompiled versions of it can be downloaded) and stick the .lib/.a and .dll/.so files in the proper places.

You will have to put all the header files in your compiler's 'include' directory, or add the current path to the compiler's "include path" (list of directories searched for header files).

You will have to specifically link the library to your program when you compile it.


There is a manual that describes how to do all this stuff.
http://gmplib.org/manual/Installing-GMP.html#Installing-GMP
Alas, I know it looks like waaaay too much to take in, but give it a go and see how far you get. The library is not too difficult to install. If you are using Windows, you'll probably want to look around for a precompiled library on the net. Google for "GMP" and your compiler's name together.

Post back if you get stuck.

[m4ster r0shi]

Wow... I've never used it before myself. I just downloaded it and it's a mess...

If you're lazy, I guess you can just copy the headers and source files you need in your project.
This could help you determine what you want -> http://gmplib.org/manual/index.html

Though, the right way would be to do it as Duoas suggests.

[pchelms]

Try declaring long long instead of just long. For grins I tried that and your program runs great!