Posts Tagged ‘multiple’

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.

Advertisements