factorization server FAQ

What algorithm does it use?
The simplest one: division by prime numbers in sequence. The server has a precalculated file of all the prime numbers up to 3162277669, which is the first prime greater than the square root of 9999999999999999999. (More precisely, a file of numbers from OEIS sequence A028334, a compact way to encode consecutive primes.)

Why does it sometimes take a long time?
In the worst case, it divides your number by 151876932 different prime numbers.

Why is there sometimes a significant difference between elapsed time and CPU time for the calculation?
It runs on a machine that's serving many people's web sites simultaneously. To not be greedy, the factorization program runs at a low priority. Also, bear in mind that in the worst case, the program reads over 150 million bytes from a disk file.

What kind of CPU does it run on?
Intel Xeon, 2.4 GHz.

What language is it written in?
C++.

Are all the factors returned known to be prime, or are they sometimes pseudoprimes?
All factors returned are honest-to-goodness primes.

Why is it limited to nineteen digits (max 9999999999999999999)?
Most 20 digit integers don't fit in 64 bits.

How does this compare to other factorization tools on the web?
It's primitive. More powerful tools are available at

• Dario Alpern's factorization page (Java applet)
• Factoris (uses a remote server)