因數分解

December 8, 2021

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

``````#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) {
n /= primes.get(i);
} else { i++; }
}
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] = {
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