Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Problem: What is the largest prime factor of the number 600851475143?

Hi, I'm really new with Python. Can anyone give me some feedback for this code? it seem to produce the correct answer

a=600851475143
x=2
while x<(a/x):
    if a%x==0: a=a/x
    else: x+=1

print a
share|improve this question
up vote 4 down vote accepted

It produces the right answer in this particular case, but it wouldn't produce the right answer for all inputs. Consider a=4. The first time you hit the while guard, x is 2 and a/x is 2, so it skips the loop and prints 4.

Is there any reason for using an op= construct for x+=1 but not for a=a/x?

I'm not a Pythonista, but I'm pretty sure it's preferred style to put the if and else blocks on a new line even if they're only one line long:

    if a%x==0:
        a/=x
    else:
        x+=1
share|improve this answer
    
It is also customary to put whitespace around operators in Python, in addition to putting if statements on their own line. – Graipher 1 hour ago

You are doing an unnecessary division every time the loop cycles:

    while x<(a/x):

To avoid this, you can define a third variable and only set it when a changes.


a may be a perfect square, as Peter Taylor mentioned. To return the correct answer in this case, use:

    while x <= (a/x):

You are comparing a changing value to another changing value. 'x' goes up while 'a/x' comes down to meet it. This works fine, but makes it hard to estimate how long the loop will run for.

    x < (a / x)

Is equivalent to:

    x < sqrt(a)

This makes it clear that, if a % x never equals 0, the loop will continue to run until x reaches \$\sqrt{a}\$. This happens for prime input, e.g. a = 600851475149.


PEP8 recommends surrounding binary operators (=, ==, +=, etc.) with a single space on either side. For directional operators (*, /, -, +, %), spaces are used to make the order of operations clear (for example, a*b + c*d). In your case, there is no order of operations to worry about, so you can leave the spacing around / and % as it is.

Adding the improvements suggested by Peter Taylor and Graipher results in:

from math import sqrt

a = 600851475143
sqrt_a = sqrt(a)
x = 2
while x <= sqrt_a:
    if a%x == 0:
        a = a/x
        sqrt_a = sqrt(a)
    else:
        x+=1
print a

Which is immediately recognizable as a correct implementation of trial division. It's mathematically equivalent to yours (except the edge case of squares Peter Taylor spotted), so, great job!

share

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.