## Smallest multiple (problem 5)

Posted: 20/06/2013 in Project Euler
Tags: , , , ,

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 ($lcm$) of all them. You read a bit more here for taking a grasp about what is this.

Let’s be $lcm (a, b)$ and $gcd (a, b)$ 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 $a$ and $b$. Then the following assertions are true:

a) For any given set of integers $\{n_{1}, ..., n_{m}\}$, the $lcm$ of all them can be carried out by the following recursive formula:

$lcm = (n_{1}, n_{2}, n_3... , n_{m}) = lcm (...lcm(lcm(n_{1}, n_{2}), n_{3}), ... , n_{m})$.

b) $lcm (a, b) = \dfrac{ab}{gcd(a, 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 $lcm$ 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.