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.

  • 1
    "Most optimal way to factorize" is a tricky question. "More optimal" might be a better question... – Thomas Andrews Aug 18 '14 at 17:29
  • 1
    @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
  • 1
    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
  • 2
    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
up vote 5 down vote accepted

All of them? The eratosthenes seive, or rather something similar, will probably win: most non-seiving systems need to duplicate their work for each prime, as opposed to getting some economy of scale. You don't need to generate any numbers higher than sqrt(highest number you care about).

Also instead of doing this in two passes, simply give each number a pair of data points when you hit it: the first prime you hit that divides it evenly, and what that number divides it into. So 522 would have the data 2, 261. Any number that doesn't have one of these is prime; all others can be factored by appending its prime factor to the factor list of its prime factor's counterpart. So factors(522) = 2, factors(261) = 2, 3, factors(87) = 2,3,3,factors(29) = 2,3,3,29.

  • I think I can implement your method of appending the prime factors in O(1) time and I never thought of this simple yet efficient way. – user1613360 Aug 18 '14 at 18:07

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.