handling large number

This is Problem 3 from Project Euler site

I'm not out after the solution, but I probably guess you will know what my approach is. To my question now, how do I handle numbe开发者_Python百科rs exceeding unsigned int?

Is there a mathematical approach for this, if so where can I read about it?

Have you tried unsigned long long or even more better/specifically uint64_t?

If you want to work with numbers bigger than the range of uint64_t [2⁶⁴-1] [64 bit integer, unsigned], then you should look into bignum: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic.

600,851,475,143 is the number given by the question and 2⁶⁴-1 is equal to 18,446,744,073,709,551,615. It is definitely big enough.

Having recently taught a kid I know prime factorization, the algorithm is trivial provided you have a list of primes.

1. Starting with 2, divide that into the target as many times as it can and leave zero remainder.
2. Take the next prime (3) and divide that into the target as in step one
3. Write down each factor you found and repeat until you run out of remainder.

Added, per request, algorithmic pseudo-code:

def factor(n):
    """returns a list of the prime factors of n"""
    factors = []
    p = primes.generator()
    while n > 1:
        x = p.next()
        while n % x == 0:
            n = n / x
            factors.append(x)
    return factors

Where successive calls to p.next() yields the next value in the series of primes {2, 3, 5, 7, 11, ...} Any resemblance of that pseudo-code to actual working Python code is purely coincidental. I probably shouldn't mention that the definition of primes.generator() is one line shorter (but one line is 50 characters long). I originally wrote this "code" because the GNU factor program wouldn't accept inputs where log₂(n) >= 40.

use

long long

in GCC

and

__int64

in VC

Use

long long

This is supported in both GCC and newer versions of Visual Studio (2008 and later, I believe).

Perhaps the easiest way to handle your problem is to use Python. Python version > 2.5 supports built-in long precision arithmetic operation. The precision is only depended on your computer memory. You can find more information about it from this link.

long long will do it for that problem. For other Project Euler problems that exceed long long, I'd probably use libgmp (specifically its C++ wrapper classes).

In Windows, if your compiler doesn't support 64 bit integers, you can use LARGE_INTEGER and ULARGE_INTEGER.