On 01/-10/-28163 02:59 PM, Chris Rebert wrote:
On Thu, Jun 9, 2011 at 1:31 AM, Ganapathy Subramanium
<sganapathy.subraman...@gmail.com> 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
For the archives, that code is:
num =3195
#num =00851475143L
prime_numbers =2]
prime_factors =]
for i in range (2,num):
for j in prime_numbers:
if i % j =0:
break
else:
prime_numbers.append(i)
print 'The Prime Numbers are : ', prime_numbers
for items in prime_numbers:
if num % items =0:
prime_factors.append(items)
print 'The prime factors are : ' , prime_factors
In the future, please avoid the unnecessary indirection of pastebins
when your code is relatively short. Including the code directly in
your post is also likely to increase the response rate you get.
Cheers,
Chris
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.
Others have pointed out various inefficiencies. But I wanted to start by
asking what this is for. Do you really have a need to factor numbers
over 2 billion? Repeatedly? In multiple runs of the program? Do you
have weeks of computer time to spend or just hours? Are you really
interested in the factors, or just whether or not a particular large
number is prime (==has anyfactors) ? If this is a homework assignment,
what's the exact assignment? Are you permitted to use other libraries,
or other languages? Are you permitted to use language features you
haven't encountered yet in class?
Assuming you have to use pure python, no extra libraries, nothing
complex, I'd just concentrate on making the current program efficient,
without major surgery.
First, you're generating far more primes than you can possibly need.
You could stop at the square root of num. Next, you're trying every
number, but you could be checking every other number (just add a step
value to the range). Those two changes eliminate the range() problem,
as the sqrt doesn't get over 2 billion till the num is over 10**18.
But more fundamentally, you're generating a big list of numbers, using
part of it once, and throwing it away. You could cache that list, store
it on disk between runs, and make it tons faster. Worse you probably
don't even need anywhere near the sqrt, unless num is prime.
So you should probably turn the problem around. Design a function that
calculates the nth prime, but that caches the work it's already done (on
disk if appropriate, but in a list if not). In the loop that's finding
the factors, simply call the first function each time, and each time you
find a factor, divide num by that so you're dealing with a smaller number.
There are faster ways to generate the primes, but now those
optimizations can be applied to the nthprime() function, and they're
independent of the factorization loop.
DaveA
--
http://mail.python.org/mailman/listinfo/python-list
