# A better way to prime factorize a set of numbers?

Let's say I have a range of numbers starting from 1 to 10^9 and I need to prime factorize each one of them.My basic algorithm is:

1.Use prime-sieve algorithms(Atkins or Eratosthenes(segmented approach more preferable to avoid Buffer overflows)) to generate primes less than 10^9.

2.Divide each n in the list with these primes in ascending order till the numerator becomes one and use of count array to store the powers of each prime needed to factorize the given number.

Even though this basic algorithm works fine I need to optimize it in any way possible to increase it's speed.I also want to know is there anyway to guess the minimum range of primes required to factorize a given number.For ex:The naive algorithm to check if a given number n is prime or not is to check for possible divisors from 2 to sqrt(n)....I want to know if it's enough to generate primes to a certain limit to prime-factorize a given n.To be more precise:

  999,824 = 2^4 × 7 × 79 × 113


My algorithm would generate primes in the range of 1 to 999824 to prime factorize the above given n and it's a solid waste of resources and degrades the performance and hence I want to know if it's possible to know in beforehand that it would be enough to find primes less than say 115 to factorize above given n.

• "Most optimal way to factorize" is a tricky question. "More optimal" might be a better question... – Thomas Andrews Aug 18 '14 at 17:29
• @ThomasAndrews Actually, optimal is already a superlative, so better is really the best (not to say: optimal) formulation :) – Hagen von Eitzen Aug 18 '14 at 17:33
• If you find a factor you can adjust the $\sqrt n$ limit to the square root of the remaining unfactorised piece. – Mark Bennet Aug 18 '14 at 17:35
• You already meantion that you need only primes up to $\sqrt n$, why do you still generate primes up to $10^9$ or $999824$? – Hagen von Eitzen Aug 18 '14 at 17:35
• Do you want an algorithm that factors all of the numbers from $1$ to $10^9$, or just some subset of those numbers? All of them is easier to do as a set, if you have enough memory. – Thomas Andrews Aug 18 '14 at 17:37