Re: Any Better logic for this problem..



On 01/-10/-28163 02:59 PM, Chris Rebert wrote:
On Thu, Jun 9, 2011 at 1:31 AM, Ganapathy Subramanium
<sganapathy.subramanium@xxxxxxxxx> 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
.