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

Groups > comp.lang.python > #7283 > 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.. Chris Angelico <rosuav@gmail.com> - 2011-06-09 19:25 +1000
    Re: Any Better logic for this problem.. Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-06-10 10:39 +1200
      Re: Any Better logic for this problem.. Chris Angelico <rosuav@gmail.com> - 2011-06-10 08:44 +1000

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

On Thu, Jun 9, 2011 at 7:06 PM, Chris Rebert <clp2@rebertia.com> wrote:
> On Thu, Jun 9, 2011 at 1:31 AM, Ganapathy Subramanium
> <sganapathy.subramanium@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:
>
> for items in prime_numbers:
>    if num % items == 0:
>        prime_factors.append(items)
>
> print 'The prime factors are : ' , prime_factors

Prime factors don't quite work that way. The prime factors of 24, for
instance, are 2, 2, 2, and 3. But if you're looking for _unique_ prime
factors, then this will work.

Rather than find all prime numbers up to num, stop at sqrt(num) - it's
not possible to have any prime factors larger than that. (Be sure to
include the square root itself; range(2,sqrt(num)) won't work if num
is a perfect square. Use range(2,sqrt(num)+1) for safety.) That will
save a fair amount of effort. Also, if you divide num by each factor
found, it'll make the numbers smaller, which may be faster.

Hope that helps!

Chris Angelico

[toc] | [next] | [standalone]

#7325

Chris Angelico wrote:

> Rather than find all prime numbers up to num, stop at sqrt(num) - it's
> not possible to have any prime factors larger than that.

That's not quite true -- the prime factors of 26 are 2 and 13,
and 13 is clearly greater than sqrt(26).

However, once you've divided out all the primes up to sqrt(n),
whatever is left, if greater than 1, must itself be prime, so
you can add it to your prime factors and stop.

-- 
Greg

[toc] | [prev] | [next] | [standalone]

#7326

On Fri, Jun 10, 2011 at 8:39 AM, Gregory Ewing
<greg.ewing@canterbury.ac.nz> wrote:
> Chris Angelico wrote:
>
>> Rather than find all prime numbers up to num, stop at sqrt(num) - it's
>> not possible to have any prime factors larger than that.
>
> That's not quite true -- the prime factors of 26 are 2 and 13,
> and 13 is clearly greater than sqrt(26).

Oops! My bad. I was thinking in terms of the "divide and conquer"
algorithm, whereby the 13 would be the residuum after dividing by 2...

> However, once you've divided out all the primes up to sqrt(n),
> whatever is left, if greater than 1, must itself be prime, so
> you can add it to your prime factors and stop.

... which is effectively the same as you describe here. It's a small
algorithmic change but an extremely advantageous one.

If you _don't_ look for the residuum, then you stop at n/2 instead of
sqrt(n). Either way, though, you don't need to list the primes all the
way up to n, which will improve performance significantly.

Chris Angelico

[toc] | [prev] | [standalone]

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

csiph-web