# Project Euler – 5

``````/**
* Problem 5
* Smallest multiple
*
* 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?
*/

#include <stdio.h>

#include <stdbool.h>
#include <stdlib.h>

#define element_t unsigned long

/* int, int */
#define is_divisible(dividend, divisor) ((dividend) == ((dividend) / (divisor)) * (divisor))

/**
*
* @NOTE For a * b = c, once a is a divisor(约数) of c, then b is also, and vice versa.
*/
static bool is_prime(const element_t num)
{
for (element_t i = 2; i * i <= num; i++)
{
if (num % i == 0) return false;
}
return true;
}

/** from 1 to end */
static element_t calc_smallest_multiple(const element_t end)
{
/* Each key is a legal multiplier */
bool is_prime_hash[end + 1];
element_t base_multiple = 1;

/* Init */
for (element_t i = 1; i < end + 1; i++)
if (is_prime(i)) {
is_prime_hash[i] = true;
base_multiple *= i;
}

/* Try to solve the divisor which is not divisible */
for (element_t i = 1; i < end + 1; i++)
if (!is_divisible(base_multiple, i))
for (element_t j = 1; j < end + 1; j++)
if (is_prime_hash[j] && is_divisible(base_multiple * j, i))
{
base_multiple *= j;
break;
}

return base_multiple;
}

int main(int argc, char const *argv[])
{
if (argc != 2) return EXIT_FAILURE;
const element_t end = atoi(argv);

printf("the smallest positive number that is evenly divisible by all of the numbers from 1 to %lu is %lu.n",
end, calc_smallest_multiple(end));

return EXIT_SUCCESS;
}`````` Web 开发者