きったんの頭_ん中☆

#ifndef GCD_H_
#define GCD_H_

/*
 * gcd.h
 * https://mind.kittttttan.info/c/gcd
 */
unsigned long gcd(unsigned long a, unsigned long b);
unsigned long lcm(unsigned long a, unsigned long b);

#endif /* GCD_H_ */

/*
 * gcd.c - Greatest Common Divisor, Least Common Multiple
 * https://mind.kittttttan.info/c/gcd
 */
#include "gcd.h"

#include <assert.h>

/*
 * Greatest Common Divisor
 * @param[in] a
 * @param[in] b
 * @return 
 */
unsigned long gcd(unsigned long a, unsigned long b) {
  unsigned long c;

  assert(b != 0);
  for (;;) {
    c = a % b;
    if (!c) { break; }
    a = b;
    b = c;
  }

  return b;
}

/*
 * Least Common Multiple
 * @param[in] a
 * @param[in] b
 * @return 
 */
unsigned long lcm(unsigned long a, unsigned long b) {
  unsigned long c;

  c = gcd(a, b);
  
  assert(c != 0);
  return a * b / c;
}