Project Euler – 5

解决 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[1]);

  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;
}

作者: YanWen

Web 开发者

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s