5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ If you want to speed things up, start with x=3 and do x+=2 - All primes (except 2) are odd, so you don't ever need to check the even ones. \$\endgroup\$ – Kylar Feb 21 '17 at 18:16
10
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ It is also customary to put whitespace around operators in Python, in addition to putting if statements on their own line. \$\endgroup\$ – Graipher Feb 21 '17 at 8:49
6
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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