The problem 5 of PE’s website says:

`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 positive number that is evenly divisible by all of the numbers from 1 to 20?`

My first impulse was to solve it by brute force, but that was not really challenging (everyone can do a loop), so I found a more elegant way to find the solution by using some basic number theory facts.

The smallest positive number that is evenly divisible by each number of a given set is just the least common multiple () of all them. You read a bit more here for taking a grasp about what is this.

Let’s be and the least common multiple and the greatest common divisor (which, as the name says, is the maximum common divisor that a set of numbers have), respectively, of two integers and . Then the following assertions are true:

a) For any given set of integers , the of all them can be carried out by the following recursive formula:

.

b)

Keeping that in mind, I wrote out three functions for solving the problem:

One function to compute the gcd of a couple of integers and another one for computing the lcm of a couple of integers too. The third one will compute the lcm of an entire set of numbers (expressed in a C array), and I will use the idea expressed in a). Of course, it’s a recursive function whose base case is exactly the of two integers.

#include <stdio.h> #include <stdlib.h> long long int gcd (long long int a, long long int b); /* Carries out the greatest common divisor of "a" and "b" */ long long int lcm (long long int a, long long int b); /* Carries out the least common multiple of "a" and "b" */ long long int lcmn (long long int nums[], int card); /* Carries out the least common multiple of the integers of the "nums[]" array, whose size is "card". */ long long int gcd (long long int a, long long int b){ long long int result; if (b == 0LL){ result = a; } else { result = gcd (b, a % b); } return result; } long long int lcm (long long int a, long long int b){ long long int leastCommonMultiple = (a*b) / gcd (a, b); return leastCommonMultiple; } long long int lcmn (long long int nums[], int card){ const int args_required_lcm = 2; long long int current_nums[args_required_lcm]; long long int result; int iteration = card; if (iteration == 2){ current_nums[0] = nums[0]; current_nums[1] = nums[1]; } else { current_nums[1] = nums[iteration - 1]; current_nums[0] = lcmn (nums, iteration - 1); } result = lcm (current_nums[0], current_nums[1]); return result; } int main (int argc, char *argv[]){ const int numbers_requested = atoi (argv[1]); long long int numbers[numbers_requested]; int i = 0; for (i = 0; i < numbers_requested; i++){ numbers[i] = i + 1LL; } printf ("%lld\n", lcmn (numbers, numbers_requested)); return 0; }

Time to compile and to run the program:

`$ (gcc -Wall -Wconversion prob5.c) && ./a.out 20`

232792560

This is the solution.

[…] Smallest multiple (problem 5) The problem 5 of PE’s website says: 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 positive number that is evenly divisible by all of the numbers from 1 to 20? My first impulse was to solve it by brute force, but that w … Thu, 20 Jun 2013 10:57:00 CDT more info… […]