因數分解

可整除兩整數的稱為公因數，可被兩數整除的整數稱為公倍數，因數分解是求某數的全部因數。

解法思路

可使用輾轉相除法（又稱歐幾里得演算法）來求最大公因數，兩數的最大公因數乘最小公倍數正好等於兩數乘積。

因數分解可使用小於輸入數的數值當作除數，去除以輸入數值，如果可以整除就視為因數，要比較快的話，可利用質數表，用小於該數的質數試試看是否可整除，求質數可參考〈Eratosthenes 篩選求質數〉。

程式實作：最大公因數、最小公倍數

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

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

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))

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)))

# encoding: UTF-8
def gcd(m, n)
    if n == 0; m else gcd(n, m % n) end
end

def lcm(m, n)
    m * n / gcd(m, n)
end
    
print "輸入 m："
m = gets.to_i
print "輸入 n："
n = gets.to_i

print "Gcd: ", gcd(m, n), "\n"
print "Lcm: ", lcm(m, n), "\n"

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))

程式實作：基於質數表的因數分解

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

// 使用 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);
        }
    }
}

# 使用 Eratosthenes 篩選求質數中的 create

def 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))

// 使用 Eratosthenes 篩選求質數中的 create

def 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))

# 使用 Eratosthenes 篩選求質數中的 create

def 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))

// 使用 Eratosthenes 篩選求質數中的 create

function 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) num

main = print $ factor 100