On 09/06/2011 09:31, Ganapathy Subramanium wrote:
Hi Guru's,
I'm working on a solution to find the prime factor of the number
This part of the code works.. http://www.pastie.org/2041584
When the number gets bigger, the range cannot iterate through bigger
number and it does not work.
When I googled , I came across creating our own range function to
solve this. I was just wondering if there was a better algorithm to
get the prime numbers / prime factors of a long number?
Any inputs is highly appreciated.
If I was attempting this problem, I would pre-compute a file of prime
numbers, in increasing order (probably use the Sieve of Erastothenes
approach).
You need a list of primes from 2 to the square root of the largest num
you will have to process.
With that, you simply work through the prime numbers,
Divide num by this prime.
If no remainder,
replace num with num // prime (so you divide by the same prime
again).
else
step on to next prime without changing num
Stop when num becomes 1.
e.g. 50 divides by 2 so factors are (2) and 25 into next
iteration with 3
25 which won't divide by 3, so factors remain (2) and 25 goes into
next iteration with 5
25 // 5 is 5 so factors become (2,5) and 5 into next iteration with 5
5 // 5 is 1 so factors are (2,5,5) and computation complete.
Ian
--
http://mail.python.org/mailman/listinfo/python-list
