I want to factor a large range of numbers (for example, say all numbers from 1 to 1 billion). I know I should be able to use some sort of sieve to do this. For example, I know every second numbers is divisible by 2, every third number is divisible by 3 etc etc. But I am struggling to implement this (using python).

Does anyone have any suggestions on a good way to implement this?

  • $\begingroup$ I would post on Stack Overflow instead. Do you need full prime factorization or just one factorization will do? E.g.. $28 = 7 \times 4$ is sufficient or $2^2 \cdot 7$ is needed? $\endgroup$ – gt6989b Jul 5 at 16:37
  • $\begingroup$ Factor all the way down to powers of primes, or just find any factor at all (since such a table would allow a user to recurse down to powers of primes)? $\endgroup$ – Eric Towers Jul 5 at 16:38
  • $\begingroup$ @gt6989b either would work $\endgroup$ – sqrt-3299 Jul 5 at 16:39
  • $\begingroup$ @EricTowers either should work $\endgroup$ – sqrt-3299 Jul 5 at 16:40
  • 1
    $\begingroup$ Be careful about "quicker". You are asking to do something $10^9$ times. Even if we can find each factor in 1 millisecond, this will require eleven and a half days to run. Also, storing a table of one billion integers in memory will be challenging (so the computation will slow down dramatically once results have to swap out to disk). $\endgroup$ – Eric Towers Jul 5 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.