Problem 5 asks: “What is the smallest number divisible by each of the numbers 1 to 20?” Instead of 20, we will consider the question for any natural number.
This is a great question as it gets you to start thinking about number theory! Specifically, how numbers are composed as the products of primes. As an example, 100 can be written as a prime decomposition this way: 2^2*5^2. In fact, all the naturals can be thought of in the form n = p1^a * p2^b * … and so on. So we can think of 1 to 20 as 1, 2, 3, 2^2, 5, 2*3, 7, 2^3, 3^3, …, 2^2*5. Back to the “smallest number divisible by each” part. Obviously, multiplying all the numbers together as has all the numbers as factors, but it isn’t the least common multiple (LCM) of the numbers. This is because some of the base primes are repeated. Consider the set 1 to 5. 1*2*3*2^2*5 = 120, but 60 is also evenly divisible by all the numbers. Since the largest exponent prime, 2^2, already contains the lower exponent prime bases, we only need to collect each prime with the largest exponent found. We can easily compute the largest exponent of each prime by calculating the logarithm of 20 in the base of each prime.
That said, the algorithm is straightforward. First, find the first n primes (20 in this case). I like the Sieve of Eratosthenes, but I adapted Euler’s Sieve for efficiency. Next, for each prime calculate floor(log_prime(20)) and store the prime raised to the result in a variable, product-wise.
Here’s my code and results via codepad.org: http://codepad.org/OYSI1OdF
bowdenc 