Problem 3: Largest Prime Factor

This problem can be trivially solved by repeatedly dividing the number by its smallest factors until only the largest prime factor remains (i.e. trial division)

n = 600851475143
i = 2
while i * i <= n:
    if n % i:
        i += 1
    else:
        n //= i
print(n)

Explained line by line:

• We start by initializing the variable n to the number whose largest prime factor we want to find, which is $600851475143$.
• We also initialize a variable i to $2 $, which is the smallest prime number and will be used to test for factors of n.
• We then enter a while loop that continues as long as i * i is less than or equal to n. This is because if n has a factor larger than its square root, the corresponding cofactor must be smaller than the square root.
• Inside the loop, we check if n is divisible by i using the modulus operator. If it is not divisible (i.e., the remainder is not zero), we increment i by $1$ to test the next integer.
• If n is divisible by i, we divide n by i using integer division (which discards any remainder). This effectively reduces n by removing the factor i.
• Once the loop exits, we print the value of n, which at this point will be the largest prime factor of the original number.

Running the above code leads to an answer of $6857$