handling large number

Question

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 numbers exceeding unsigned int?

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

Answer 1

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.

Answer 2

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.