So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #3 statement is —

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

There is no need to build a list of every divisor and test each one for primality. Instead, divide each factor out as soon as it is found. This makes the remaining number smaller throughout the search.

number = 600_851_475_143
largest_factor = 1

while number % 2 == 0:
    largest_factor = 2
    number //= 2

factor = 3
while factor * factor <= number:
    while number % factor == 0:
        largest_factor = factor
        number //= factor
    factor += 2

if number > 1:
    largest_factor = number

print(largest_factor)

After removing every possible factor up to the square root of the remaining number, anything left must itself be prime. The answer is 6857, found in constant space and at most square-root time.