Project Euler 5: Find the Lowest Common Multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

This means that you have to find the lowest common multiple of 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 and 20. Here is a Perl script that does that very thing through brute force:

1
2
3
4
5
6
7
8
9
10

for ( my $n = 20; 1; $n++ ) { # do forever
	for ( 1..20 ) { # for every integer from 1 to 20
		if ( $n % $_ ) { # if $n is not divisible by the integer..
			last; # ..end the for-loop
		}
		if ( $_ == 20 ) { # if $n has been divisible by every number up to 20..
			die $n; # ..print the result and terminate the script
		}
	}
}

However, this script will probably take 20 minutes or so to interpret. In order to optimize it, we could first remove some of the numbers that are divided with. 1 is unnecessary since all natural numbers are divisible by 1. We don’t need 2, either, since all numbers divisible by multiples of 2 (such as 4 or 18) are divisible by 2, too. This way, we can deduce away all of the numbers except: 11, 12, 13, 14, 15, 16, 17, 18, 19 and 20.

This isn’t the end of the optimization: Why are we incrementing only by 1? If we increment $n by 20 every loop, we will still get all values that are divisible by 20. This way, we can make the code a lot faster — after applying this step, I found the answers in 16 seconds instead of 700 seconds. This is the final script, with lines 1, 2 and 6 changed.

1
2
3
4
5
6
7
8
9
10

for ( my $n = 20; 1; $n += 20 ) { # do forever, incrementing by 20
	for ( 11,12,13,14,15,16,17,18,19 ) { # for the relevant integers
		if ( $n % $_ ) { # if $n is not divisible by the integer..
			last; # ..end the for-loop
		}
		if ( $_ == 19 ) { # if $n has been divisible by every number up to 19..
			die $n; # ..print the result and terminate the script
		}
	}
}

Maybe Related?

• Project Euler 1: Sum of the Multiples of 3 and 5
• Project Euler 10: Sum of First Primes
• Project Euler 8: Greatest Product of Consecutive Digits in String
• Project Euler 9: Pythagorean Triplets, Sum=1000
• Project Euler 6: Square of Sums Minus Sum of Squares