Euler Project problem #3

Question

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

Answer 1

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

Answer 2

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 /= 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!