[演算法] 最大公因數(GCD) & 最小公倍數(LCM)

C++

int gcd(int a, int b) // recursion
{
    if (!b) return a; // if (b == 0)
    return gcd(b, a % b);
}

int gcd(int a, int b) // loop
{
    while (b)
    {
        a = a % b;
        swap(a, b);
    }
    return a;
}

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

記得要注意 int 所能表示的範圍。

Python

from functools import reduce


def gcd(*numbers):
    # from fractions import gcd # before python 3.5
    from math import gcd # after python 3.5
    return reduce(gcd, numbers)


def lcm(*numbers):
    def lcm(a, b):
        return (a * b) // gcd(a, b)
    return reduce(lcm, numbers)

Java

package test;

import java.math.BigInteger;
import java.util.Arrays;

public class Test
{
  public static long gcd(long ...args)
  {
    if (args.length == 0) return 0;
    return Arrays.stream(args).reduce(Test::gcd).getAsLong();
  }

  public static long gcd(long a, long b)
  {
    return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
  }

  public static long lcm(long a, long b)
  {
    return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b))
        .divide(BigInteger.valueOf(gcd(a, b))).longValue();
  }

  public static long lcm(long ...args)
  {
    if (args.length == 0) return 0;
    return Arrays.stream(args).reduce(Test::lcm).getAsLong();
  }

  public static void main(String[] args)
  {
    System.out.println(gcd(2 * 2 * 2 * 3 * 5 * 7 * 7 * 11,
        2 * 2 * 3 * 5 * 7, 2 * 2 * 3 * 5 * 7 * 11));
    System.out.println(gcd(5));
    System.out.println(lcm(2 * 2 * 3 * 5, 2 * 2, 3 * 7 * 11));
  }
}

Java 的版本記得要修改 1128 行的地方,還有注意數值範圍,如果結果超過 long 所能表達的範圍要改成使用 BigInteger

Show Comments