Project Euler problem 5

Source code available on GitHub.

This problem seems simpler than the last few to me.

It’s fairly clear how to proceed. We can just check every multiple of 20, starting at 20 and adding 20 every time. If the multiple is divisible by all of the numbers 1 through 19, we stop and print the output.

To check every multiple of 20 indefinitely, we use a `while` loop:

i = 20
while True:
    # Check stuff here
    i += 20

To check whether i is divisible by all the numbers 19, 18, 17 and so on, we just do a for loop:

for j in range(19,0,-1):
    if i % j != 0:
        # Failed test
# Passed test

Note that in the range function we’re starting at 20 and going down to 1 rather than the other way round (the -1 tells range() to add -1 each time rather than 1): this is more efficient as it’s much less likely for a number to be divisible by, say, 19 than it is for it to be divisible by, say, 3.

The number i has only passed the test if we get through the whole for loop without the if statement ever being triggered. We only want to do the increment and try again if `i` fails the check, so we put i += 20 inside the if statement:

i = 20
while True:
    for j in range(19,0,-1):
        if i % j != 0:
            i += 20
            break

The break statement forces us out of the for loop and consequently restarts the while loop with the new value of i.

Now, if we do indeed get to the end of the for loop with every j being a factor of i,  the current value of j will be 1 (as the for loop iterates downwards). Hence, if this is the case, i is our answer. We’ll hold it in some other variable smallest_multiple and break out of the for loop:

i = 20
while True:
    for j in range(19,0,-1):
        if i % j != 0:
            i += 20
            break
        if j == 1: # If checked all of them and still here
            smallest_multiple = i
            break

The last thing to do is check whether smallest_multiple actually holds a value, and if so break out of the whole while loop and print it off. We’ll set smallest_multiple = 0 initially to help us.

We’re done! Code below:

smallest_multiple = 0
i = 20
while True:
    for j in range(19,0,-1):
        if i % j != 0:
            i += 20
            break
        if j == 1: # If checked all of them and still here
            smallest_multiple = i
            break
    if smallest_multiple != 0:
        break
print(smallest_multiple)