# Factoring Range of Numbers

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?

• 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? – gt6989b Jul 5 at 16:37
• 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)? – Eric Towers Jul 5 at 16:38
• @gt6989b either would work – sqrt-3299 Jul 5 at 16:39
• @EricTowers either should work – sqrt-3299 Jul 5 at 16:40
• 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). – Eric Towers Jul 5 at 17:20