Docs


Problem 5: Smallest Multiple

Problem

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?

Solution

/*
 * Smallest Multiple
 * Problem 5 <https://projecteuler.net/problem=5>
 *
 * Project Euler
 *
 * By Ankit R Gadiya
 */

#include <stdio.h>
#include <stdbool.h>

int gcd (int u, int v);
int lcm (int u, int v);

int main (void)
{
	int p, d, product = 1, limit = 20;
	bool isPrime;

	for (p = 2; p < limit; p++)
	{
		isPrime = true;

		for (d = 2; d < p && isPrime; d++)
		{
			if (p % d == 0)
			{
				isPrime = false;
			}
		}

		if (isPrime) {
			product *= p;
		} else {
			product = lcm (product, p);
		}
	}

	printf("Answer: %i\n", product);
	return 0;
}

int lcm (int u, int v)
{
	int     ans = u * v/ gcd (u, v);

	return ans;
}

int gcd (int u, int v)
{
	int temp;

	while (v != 0)
	{
		temp = u % v;
		u = v;
		v = temp;
	}

	return u;
}

prob5.c

Result

232792560