Any Better logic for this problem..

[Dave Angel]

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