How to find all the prime factors in a unsigned long long integer?

Question

I have a assignment to find all the prime factors of a number...

I need to write a function that takes a number and tells me all the prime factors of the number. For example:

• n=350 prime factors:2 5 5 7

(I pass to the function a number in the range 0 to 18446744073709551615 - the maximum number is largest number that fits in a 64-bit unsigned long long integer.)

Answer 1

That's a hard problem, and one of the main reasons for all the research into quantum computers. Take a look at Shor's Algorithm. Simple brute-force without optimizations would take something like 1000 years, although in this specific case (64-bit integers), you should be able to reduce your run-time to just a few minutes.

Assuming you have a trivial case of (at most) one large prime factor, you can speed up significantly by doing something like counting up from 2 and trying each number (multiple times if it works; 12 would be 2, 2, and 3 for example). After you find a factor, reduce your target number by that factor and test if the new target is prime.

To speed it up further, you could do processing across multiple threads, with each in charge of a range of divisors. You could run primality testers on one or more threads, providing primes to the testing thread so you are only trying to divide by prime numbers.

You could even search from the top of the range down, if you think the person providing the value is trying to be tricksome, although with the density of prime numbers being so much higher at the low end, this likely will not help.

The main thing to remember, though, that the largest possible factor of X, besides for X itself, is the square-root of X. Each time you find a factor, the largest possible remaining factor decreases significantly.