# 最大公因數、最小公倍數、因數分解

## 解法

• C（不用質數表的因數分解）
``#include <stdio.h> #include <stdlib.h> int main(void) {    int n;     printf("請輸入整數：");     scanf("%d", &n);     printf("%d = ", n);     int i;    for(i = 2; i * i <= n;) if(n % i == 0) {         printf("%d * ", i);         n /= i;     } else { i++; }    return 0; } ``

• C
``#include <stdio.h> #include <stdlib.h> int gcd(int m, int n) {    while(n != 0) {         int r = m % n;         m = n;         n = r;     }     return m;}int lcm(int m, int n) {    return m * n / gcd(m, n);}int main(void) {     int m, n;     printf("輸入兩數：");     scanf("%d %d", &m, &n);     printf("Gcd：%d\n", gcd(m, n));     printf("Lcm：%d\n", lcm(m, n));         return 0; } ``

• Java
``public class Main {    public static int gcd(int m, int n) {        return n == 0 ? m : gcd(n, m % n);    }    public static int lcm(int m, int n) { return m * n / gcd(m, n);}    public static void main(String[] args) {        System.out.printf("GCD of (10, 4) = %d", gcd(10, 4));        System.out.printf("LCM of (10, 4) = %d", lcm(10, 4));    }}``

• Python
``def gcd(m, n):    return m if n == 0 else gcd(n, m % n)def lcm(m, n):    return m * n // gcd(m, n)    m = int(input("輸入 m："))n = int(input("輸入 n："))print("Gcd: ", gcd(m, n))print("Lcm: ", lcm(m, n))``

• Scala
``def gcd(m: Int, n: Int): Int = if(n == 0) m else gcd(n, m % n)def lcm(m: Int, n: Int) = m * n / gcd(m, n)println("Gcd of (10, 4) = %d".format(gcd(10, 4)))println("Lcm of (10, 4) = %d".format(lcm(10, 4)))``

• Ruby
``# encoding: Big5def gcd(m, n)    if n == 0; m else gcd(n, m % n) endenddef lcm(m, n)    m * n / gcd(m, n)end    print "輸入 m："m = gets.to_iprint "輸入 n："n = gets.to_iprint "Gcd: ", gcd(m, n), "\n"print "Lcm: ", lcm(m, n), "\n"``

• JavaScript
``function gcd(m, n) { return n === 0 ? m : gcd(n, m % n); }function lcm(m, n) { return m * n / gcd(m, n); }print('GCD of (10, 4) = ' + gcd(10, 4));print('LCM of (10, 4) = ' + lcm(10, 4));``

``gcd' m n = if n == 0 then m else gcd n (m `mod` n)lcm' m n = m * n `div` (gcd m n)main = do    putStrLn ("Gcd of (10, 4) = " ++ (show \\$ gcd' 10 4))    putStrLn ("Lcm of (10, 4) = " ++ (show \\$ lcm' 10 4))``

• C
``#include <stdio.h> #include <stdlib.h> #define N 1000 void create(int*);       // 建立質數表void filter(int*, int);void factor(int, int*, int*);  // 因數分解int main(void) {     int primes[N + 1] = {0};    create(primes);        printf("請輸入一數：");     int num;    scanf("%d", &num);         int factors[N / 2 + 1] = {0};    factor(num, factors, primes);         int i;    for(i = 0; factors[i] != 0; i++) {        printf("%d ", factors[i]);    }        return 0; } void create(int* primes) {    primes[2] = primes[3] = primes[5] = 1;        int i;    for(i = 1;6 * i + 5 <= N; i++) {        primes[6 * i + 1] = primes[6 * i + 5] = 1;     }    if(6 * i + 1 <= N) { primes[6 * i + 1] = 1; }        int n;    for(n = 0;(6 * n + 5) * (6 * n + 5) <= N; n++) {        filter(primes, 6 * n + 1);        filter(primes, 6 * n + 5);    }         if((6 * n + 1) * (6 * n + 1) <= N) { filter(primes, 6 * n + 1); }  }void filter(int* primes, int i) {    if(primes[i]) {         int j;        for(j = 2; j * i <= N; j++) {            primes[j * i] = 0;         }    }}void factor(int num, int* factors, int* primes) {     int i, j;    for(i = 2, j = 0; i * i <= num;) if(primes[i] && num % i == 0) {        factors[j++] = i;        num /= i;    } else { i++; }    factors[j] = num;}``

• Java
``// 使用 Eratosthenes 篩選求質數 中的 Prime import java.util.*;public class Factor {    public static List<Integer> factor(int n) {        List<Integer> primes = Prime.create(n / 2);        return factor(n, primes);    }        public static List<Integer> factor(int n, List<Integer> primes) {        List<Integer> factors = new ArrayList<>();        for(int i = 0; primes.get(i) <= Math.sqrt(n);) {             if(n % primes.get(i) == 0) {                 factors.add(primes.get(i));                n /= primes.get(i);             } else { i++; }        }         factors.add(n);              return factors;    }    public static void main(String[] args) {        for(Integer f : factor(100)) {            System.out.printf("%d ", f);        }    }}``

• Python
``# 使用 Eratosthenes 篩選求質數 中的 createdef factor(n):    def ft(ps, num):        if ps[0] ** 2 > num:            return [num]        else:            return (ps[0:1] + ft(ps, num // ps[0])                     if num % ps[0] == 0 else ft(ps[1:], num))                        return ft(create(n // 2), n)    print(factor(100))``

• Scala
``// 使用 Eratosthenes 篩選求質數 中的 createdef factor(n: Int) = {    def ft(ps: List[Int], num: Int): List[Int] = {        if(math.pow(ps.head, 2) > num) List(num)        else if(num % ps.head == 0) ps.head :: ft(ps, num / ps.head)             else ft(ps.tail, num)    }    ft(create(n / 2), n)}    print(factor(100))``

• Ruby
``# 使用 Eratosthenes 篩選求質數 中的 createdef factor(n)    ft = ->(ps, num) {        if ps[0] ** 2 > num            [num]        else            if num % ps[0] == 0                ps[0,1] + ft.call(ps, num / ps[0])            else                ft.call(ps[1, ps.size], num)            end        end    }    ft.call(create(n / 2), n)end    print(factor(100))``

• JavaScript
``// 使用 Eratosthenes 篩選求質數 中的 createfunction factor(n) {    var primes = create(parseInt(n / 2));    var factors = [];    for(var i = 0; primes[i] <= Math.sqrt(n);) {         if(n % primes[i] === 0) {             factors.push(primes[i]);            n /= primes[i];         } else { i++; }    }     factors.push(n);    return factors;}print(factor(100));``

``{- 使用 Eratosthenes 篩選求質數 中的 create -}factor n = ft (create (n `div` 2)) n    where ft ps num =              if (head ps) ^ 2 > num then [num]              else if num `mod` (head ps) == 0 then                        (head ps) : ft ps (num `div` (head ps))                   else ft (tail ps) nummain = print \\$ factor 100``