Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #7282 > unrolled thread

Re: Any Better logic for this problem..

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Any Better logic for this problem.. Ian <hobson42@gmail.com> - 2011-06-09 10:19 +0100

#7282 — Re: Any Better logic for this problem..

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

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web