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?

Bamberger

The largest prime factor of 600851475143 is less than 10000. As someone mentioned below, python is ideally suited to this task and I just used 44 milliseconds factoring your target. I'm not being coy with the factor, just trying not to give a spoiler. – Leporide

I have not python compiler installed though, I guess I will leave the c++ code running until it is done with the procedure...haha – Bamberger

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.

Damask

Suggest you try again, @klw, and this time do it right :-) 64 bits is heaps more than you need. – Cerotype

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.

Leporide

I did not catch the steps (my english sucks). can you possibly show me some calc examples? – Bamberger

Added per request. Did you get your factors yet? – Leporide

Answer 3

use

long long

in GCC

and

__int64

in VC

Lomeli

Answer 4

Use

long long

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

Ejaculatory

Answer 5

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.

Quizzical

Answer 6

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).

Gaia

Answer 7

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

Vanover