說明
可整除兩數的稱之為公因數，可使用輾轉相除法來求最大公因數，可被兩數整除的某數稱之為公倍數，兩數的最大公因數乘最小公倍數正好等於兩數乘積。因數分解就是求某數的所有因數。解法
因數分解就是使用小於輸入數的數值當作除數，去除以輸入數值，如果可以整除就視為因數。例如：- 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;
}
要比較快的解法就是求出小於該數的所有質數，並試試看是不是可以整除，求質數的問題是另一個課題，請參考 Eratosthenes 篩選求質數。
最大公因數、最小公倍數：C Java Python Scala Ruby JavaScript Haskell
使用質數表因數分解：C Java Python Scala Ruby JavaScript Haskell
#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: Big5
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