When unsigned long long isn't long enough

[captdrizzle]

I am trying to solve a project euler problem just so I can get more experience. The problem states:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

However unsigned long long or unsigned double isn't big enough to hold this number to do calculations on it.
I using Dev-C++ as my IDE. What can I do to work with this number?


My code (if anybody is interested) is:

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;


    unsigned long long subject = 600851475143;
    bool isPrime(long long);
    bool isFactor(long long , long long);
    
    
int main()
{

    long long placeA = 0;
    long long placeB = 0;
    long long counter = 1;
    
    while(counter < subject){
                      
    placeB = placeA;
    if(isFactor(counter, subject) && isPrime(counter))              
                  placeA = counter;
                  
    counter++;
    //    cout << placeA << " " << placeB << " " << counter << endl;            
    }
    cout << fixed << setprecision(0);
    cout << placeA << " " << placeB << " " << counter << endl;

}


bool isFactor(long long numA, long long subjectA)
{
     if(0 == (subjectA % numA))

        return true;
     else
         return false;

}

bool isPrime(long long num)
{

    long long denom = 2;
    bool prime = true;
    if (num == 4)
       prime = false;
          while (denom < num/2){ 
                
                if(0 == (num % denom)){
                     prime = false;
                }                 
                                  
                if(prime == false)
                return false;
                                             
                denom = denom + 1;
                
          }
        return true;
    
}

[firedraco]

Grab a bignum library from somewhere.

[blueberry]

but that doesn’t help him with experience...

[shacktar]

@captdrizzle: what exactly is the problem you're experiencing? unsigned long long (and long long for that matter) is big enough to store 600851475143 and to calculate its prime factors. Likely there's a problem with your algorithm.

[blueberry]

I though long longs only work on 64 bit cpu...

[captdrizzle]

With the code above, Dev-C++ gives me the error message:

8 C:\CPP\Euler3\main.cpp integer constant is too large for "long" type

If I put in a smaller number it works just fine.

I tried using a bignum library, but I am unsure of how to implement it.

[shacktar]

Apparently, for Dev-C++, you need to use unsigned long long int or long long int.

http://gcc.gnu.org/onlinedocs/gcc/Long-Long.html

[captdrizzle]

I get the same error message with unsigned long long int. I was able to solve the euler problem by taking the number as input into a unsigned long long type instead of declaring it with "subject".
Problem aside, does anybody know what caused this? If I want to work with exceptionally large numbers in the future do I have to take them as user/file input?

[shacktar]

Maybe this will work?

unsigned long long /*int*/ subject = 600851475143ULL;

This is a little strange for me because, using Visual Studio, I can just do this no problem:

unsigned long long subject = 600851475143;

[captdrizzle]

Adding the ULL to the end of the number did it. I wonder why that is. Either way, thank you! ULL is just one of those tricks I will have to remember.

[firedraco]

ULL is a suffix that tells the compiler "interpret the number as an unsigned long long integer" instead of a normal, as it seemed to be (which apparently it was truncated before assigning it).