All factors of big numbers in C/C++

Question

I am trying to find out all factors of numbers which are of the order of 10^18... But there are time constraints which are creating a problem. What i did was to use Sieve of Eratosthenes to find factors and then store the factors but it is slow.......

Answer 1

If space is not a problem, you could store a list of prime numbers up to 10^9 (lists are available for download) and use it to factorize any number up to 10^18. You could also use factoring algorithms (like pollard's rho, or others).

Answer 2

I would really recommend to read Wiki article on this Integer factorization: http://en.wikipedia.org/wiki/Integer_factorization

General purpose factorization methods are slow. However, may be try to use some special purpose methods.

Answer 3

The problem with the idea of storing a list of primes p<=10^9 to factor numbers N<=10^18 is that for any particular N you would still need to loop over the primes p<=sqrt(N) and check whether or not N%p==0. This is not the fastest way to do business.

It's not clear from your question if you want to factor a bunch of numbers that are order 10^18, or if you want to factor all numbers N<=10^18. The first case is doable depending on how many N you want to factor and how fast it needs to be. The second case, factoring all numbers N<=10^18, is not doable, because that would entail more than 10^18 operations (at least one for each number to be factored). Considering that computers can do on the order of 10^9 operations per second, and there are on the order of 10^7 seconds in the year, you'd be factoring for a long time.

If you just want to factor a bunch of numbers N on the order of 10^18, then there are lots of ways to do this. The "best" way depends on the properties of the specific numbers. For example, random integers around 10^18 are a lot easier to factor on average than integers that are the product of two primes each of order 10^9, because small factors can be eliminated with trial division before moving to a more sophisticated algorithm. This is more a computational number theory question than a programming question. If this is your question, I recommend to it to the Factoring section of mersenneforum.org.

If you want a quick and dirty solution that is not ridiculously slow then don't reinvent the wheel. Try for example GMP-ECM or see if PARI/GP can solve your problem.