Handling large quantities

Question

This is Problem 3 from Project Euler

I will not go after the decision, but I probably guess that you will understand that my approach. To my question now, how do I handle numbers superior to 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 better / specifically uint64_t ?

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

600,851,475,143 is the number asked by the question, and 2 ⁶⁴ -1 is equal to 18 446 744 073 709 551 615. This is definitely quite large.

Answer 2

Having recently trained a child, I know the basic factorization, the algorithm is trivial if you have a list of primes.

• Starting at 2, divide this by the target as many times as you can, and leave zero balance.
• Take the following simple (3) and divide it into a target, as in the first step
• Record each found factor and repeat until you finish the remainder.

Algorithmic pseudocode added for each request:

 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 

If consecutive calls to p.next() give the following value in a series of primes {2, 3, 5, 7, 11, ...} Any similarity between this pseudo-code and the actual working Python code is purely random. I probably shouldn't mention that the definition of primes.generator() is one line shorter (but one line 50 characters long). I originally wrote this “code” because the GNU factor program did not accept input, where log ₂ (n)> = 40.

Answer 3

use

 long long 

in gcc

and

 __int64 

in vc

Answer 4

Using

 long long 

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

Answer 5

Perhaps the easiest way to handle your problem is to use Python. Python version> 2.5 supports the built-in exact arithmetic operation. Accuracy depends only on the memory of your computer. You can find more information about this from the link .

Answer 6

long long will do this for this problem. For other Project Euler problems that exceed long long , I would probably use libgmp (in particular, its C ++ shell classes ).

Answer 7

On Windows, if your compiler does not support 64-bit integers, you can use LARGE_INTEGER and ULARGE_INTEGER .