Calculating factorization for large numbers

Question

My mission is to calculate the factorization of large numbers, for example, from $start=1e11$ to $end=1e12$.

To do that, one approach that I was thinking of is to calculate for each number his factorization by dividing prime numbers from it, assuming I have a large data set of prime numbers. This will take roughly $O(log\left(n\right))$ for each number or $O(\frac{n}{log\left(n\right)})$ by $PNT$ theorem (If the number is prime), but it takes too long.

A different approach that I was thinking of is to use some kind of combinatorics argument like this thread: Number of possible products

If I have a large data set of prime numbers, I can calculate all the possible products from the set and check if it fits into the range, attacking the problem in a more global manner instead of individually, but I don't know how to exactly implement it.

My question is, what is the right approach? And how can I implement it in my calculation?

Answer 1

An algorithm allowing quite fast factoring of any number up to N using N bytes of storage:

Assign an index starting at 0 to each prime p with p^2 <= N.

Using an operation similar to the sieve of Eratosthenes, for each n >= 2 store -1 if n is prime, and the index k of n’s smallest prime factor otherwise. This lets you factor n fast: Take the index k from the table. If k = -1 then n is prime, otherwise let p be the prime at index k, output p, and factor n/p.

Reduce the storage to 1 byte per number: Instead of -1 or k, store 255 or k modulo 255. If the table contains 255, n is prime. Otherwise try the primes at index k, k+255, k+510 etc. until you find a divisor p, output p and factor n/p.

Reduce the storage by a factor 4.375: Out of every 210 consecutive integers, all but 48 are divisible by 2, 3, 5 or 7. So create a table that uses only 48 out of 210 consecutive entries. To factor n >= 2, output factors p = 2, 3, 5, 7 and divide n by p as long as n is divisible by p, and use the previous algorithm to factor n if n > 1.

The trial division is quite fast: Say N = 10^12, primes <= 1,000,000, there are maybe 100,000, you try one in 255 which is at most 400, but usually the prime factor is found quite early. You can reduce the storage further by not storing numbers divisible by 11 or 13 (5,760 out of 30,030 or about one in 5.21).