如何用程式進行質因數分解和尋找最大公因數與最小公倍數？

若正整數#{{a}}#除以正整數#{{b}}#可以整除，則稱#{{b}}#為#{{a}}#的因數(Factor)，#{{a}}#為#{{b}}#的倍數(Multiple)，#{{1}}#是所有正整數最小的因數，任意正整數最大的因數就是該正整數本身。若#{{a}}#同時是#{{x}}#和#{{y}}#的因數，則稱#{{a}}#是#{{x}}#和#{{y}}#的公因數(Common Divisor)，如果#{{a}}#是#{{x}}#和#{{y}}#的公因數中最大的一個，則稱#{{a}}#是#{{x}}#和#{{y}}#的最大公因數(Greatest Common Divisor，簡稱GCD)。若#{{a}}#同時是#{{x}}#和#{{y}}#的倍數，則稱#{{a}}#是#{{x}}#和#{{y}}#的公倍數(Common Multiple)；如果#{{a}}#是#{{x}}#和#{{y}}#的公倍數中最小的一個，則稱#{{a}}#是#{{x}}#和#{{y}}#的最小公倍數(Least Common Multiple，簡稱LCM)。

質因數與質因數分解

若因數是質數(Prime)，則稱其為質因數(Prime Factor)。找出一個正整數的所有質因數之行為，就稱為「質因數分解」(Prime Factorization)。若要對數值不大的正整數#{{N}}#做質因數分解，可以利用試除法(Trial Division)，找出#{{2}}#到#{{\sqrt{N}}}#之間的質數，來一個一個測試#{{N}}#是否能夠被這個範圍的質數整除。如果找不到，那#{{N}}#的質因數就是#{{N}}#的自身。

有關於質數的說明，可以參考這篇文章：

https://magiclen.org/prime-number/

程式如下：

pub fn prime_factorize(mut n: i32) -> Vec<i32> {
    if n < 2 {
        Vec::new()
    } else if n <= 3 {
        vec![n]
    } else {
        let mut prime_factors = Vec::new();

        let primes = get_prime_numbers(2, (n as f64).sqrt().floor() as i32);

        for prime in primes {
            while n > 1 && n % prime == 0 {
                prime_factors.push(prime);
                n /= prime;
            }
        }

        if prime_factors.is_empty() {
            prime_factors.push(n);
        }

        prime_factors
    }
}

pub fn get_prime_numbers(mut a: i32, b: i32) -> Vec<i32> {
    let mut result = Vec::new();

    match a {
        0 | 1 => {
            if b >= 3 {
                result.push(2);
                result.push(3);

                a = 5;
            } else if b == 2 {
                result.push(2);
                return result;
            } else {
                return result;
            }
        }
        2 => {
            result.push(2);

            if b == 2 {
                return result;
            }

            result.push(3);
            a = 5;
        }
        3 => {
            result.push(3);
            a = 5;
        }
        x if x % 2 == 0 => {
            a += 1;
        }
        _ => ()
    }

    'outer: for n in (a..=b).step_by(2) {
        let m = n % 6;

        if m != 1 && m != 5 {
            continue;
        }

        let n_sqrt = (n as f64).sqrt().floor() as i32;

        if n_sqrt >= a {
            for i in (5..a).step_by(6) {
                if n % i == 0 || n % (i + 2) == 0 { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
                    continue 'outer;
                }
            }

            for p in result.iter().copied() {
                if p > n_sqrt {
                    break;
                }

                if n % p == 0 {
                    continue 'outer;
                }
            }
        } else {
            for i in (5..=n_sqrt).step_by(6) {
                if n % i == 0 || n % (i + 2) == 0 { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
                    continue 'outer;
                }
            }
        }

        result.push(n);
    }

    result
}

public static ArrayList<Integer> primeFactorize(int n) {
    if (n < 2) {
        return new ArrayList<>();
    } else if (n <= 3) {
        final ArrayList<Integer> primeFactor = new ArrayList<>(1);

        primeFactor.add(n);

        return primeFactor;
    } else {
        final ArrayList<Integer> primeFactors = new ArrayList<>();

        final ArrayList<Integer> primes = getPrimeNumber(2, (int) Math.floor(Math.sqrt(n)));

        for (final int prime : primes) {
            while (n > 1 && n % prime == 0) {
                primeFactors.add(prime);
                n /= prime;
            }
        }

        if (primeFactors.isEmpty()) {
            primeFactors.add(n);
        }

        return primeFactors;
    }
}

public static ArrayList<Integer> getPrimeNumber(int a, final int b) {
    final ArrayList<Integer> result = new ArrayList<>();

    switch (a) {
        case 0:
        case 1:
            if (b >= 3) {
                result.add(2);
                result.add(3);

                a = 5;
            } else if (b == 2) {
                result.add(2);
                return result;
            } else {
                return result;
            }
            break;
        case 2:
            result.add(2);

            if (b == 2) {
                return result;
            }

            result.add(3);
            a = 5;
            break;
        case 3:
            result.add(3);
            a = 5;
            break;
        default:
            if (a % 2 == 0) {
                ++a;
            }
    }

    outer:
    for (int n = a; n <= b; n += 2) {
        final int m = n % 6;

        if (m != 1 && m != 5) {
            continue;
        }

        final int nSqrt = (int) Math.floor(Math.sqrt(n));

        if (nSqrt >= a) {
            for (int i = 5; i < a; i += 6) {
                if (n % i == 0 || n % (i + 2) == 0) { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
                    continue outer;
                }
            }

            for (final int p : result) {
                if (p > nSqrt) {
                    break;
                }

                if (n % p == 0) {
                    continue outer;
                }
            }
        } else {
            for (int i = 5; i <= nSqrt; i += 6) {
                if (n % i == 0 || n % (i + 2) == 0) { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
                    continue outer;
                }
            }
        }

        result.add(n);
    }

    return result;
}

function primeFactorize(n: number) {
    if (n < 2) {
        return [];
    } else if (n <= 3) {
        return [n];
    } else {
        const primeFactors = [];

        const primes = getPrimeNumber(2, Math.floor(Math.sqrt(n)));

        for (const prime of primes) {
            while (n > 1 && n % prime === 0) {
                primeFactors.push(prime);
                n /= prime;
            }
        }

        if (primeFactors.length === 0) {
            primeFactors.push(n);
        }

        return primeFactors;
    }
}

function getPrimeNumber(a: number, b: number) {
    const result: number[] = [];

    switch (a) {
        case 0:
        case 1:
            if (b >= 3) {
                result.push(2);
                result.push(3);

                a = 5;
            } else if (b === 2) {
                result.push(2);
                return result;
            } else {
                return result;
            }
            break;
        case 2:
            result.push(2);

            if (b === 2) {
                return result;
            }

            result.push(3);
            a = 5;
            break;
        case 3:
            result.push(3);
            a = 5;
            break;
        default:
            if (a % 2 === 0) {
                a += 1;
            }
    }

    if (a < 2 && b >= 2) {
        result.push(2);

        a = 3;
    } else if (a % 2 === 0) {
        if (a === 2) {
            result.push(2);
        }

        a += 1;
    }

    outer:
    for (let n = a;n <= b;n += 2) {
        const m = n % 6;

        if (m !== 1 && m !== 5) {
            continue;
        }

        const nSqrt = Math.floor(Math.sqrt(n));

        if (nSqrt >= a) {
            for (let i = 5;i < a;i += 6) {
                if (n % i === 0 || n % (i + 2) === 0) { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
                    continue outer;
                }
            }

            for (const p of result) {
                if (p > nSqrt) {
                    break;
                }

                if (n % p === 0) {
                    continue outer;
                }
            }
        } else {
            for (let i = 5;i <= nSqrt;i += 6) {
                if (n % i === 0 || n % (i + 2) === 0) { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
                    continue outer;
                }
            }
        }

        result.push(n);
    }

    return result;
}

func PrimeFactorize(n int) []int {
	if n < 2 {
		return []int{}
	} else if n <= 3 {
		return []int{n}
	} else {
		primeFactors := make([]int, 0)

		primes := GetPrimeNumber(2, int(math.Floor(math.Sqrt(float64(n)))))

		for _, prime := range primes {
			for n > 1 && n%prime == 0 {
				primeFactors = append(primeFactors, prime)
				n /= prime
			}
		}

		if len(primeFactors) == 0 {
			primeFactors = append(primeFactors, n)
		}

		return primeFactors
	}
}

func GetPrimeNumber(a int, b int) []int {
	result := make([]int, 0)

	switch a {
	case 0, 1:
		if b >= 3 {
			result = append(result, 2)
			result = append(result, 3)

			a = 5
		} else if b == 2 {
			result = append(result, 2)
			return result
		} else {
			return result
		}
	case 2:
		result = append(result, 2)

		if b == 2 {
			return result
		}

		result = append(result, 3)
		a = 5
	case 3:
		result = append(result, 3)
		a = 5
	default:
		if a%2 == 0 {
			a++
		}
	}

outer:
	for n := a; n <= b; n += 2 {
		m := n % 6

		if m != 1 && m != 5 {
			continue
		}

		nSqrt := int(math.Floor(math.Sqrt(float64(n))))

		if nSqrt >= a {
			for i := 5; i < a; i += 6 {
				if n%i == 0 || n%(i+2) == 0 { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
					continue outer
				}
			}

			for _, p := range result {
				if p > nSqrt {
					break
				}

				if n%p == 0 {
					continue outer
				}
			}
		} else {
			for i := 5; i <= nSqrt; i += 6 {
				if n%i == 0 || n%(i+2) == 0 { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
					continue outer
				}
			}
		}

		result = append(result, n)
	}

	return result
}

最大公因數

要求兩正整數#{{a}}#、#{{b}}#的最大公因數，可以利用上面介紹的方式找出兩數的所有質因數，再把所有共同的質因數相乘，積就是最大公因數了(短除法的應用)……不過這樣做其實挺慢的，以下介紹用輾轉相除法求最大公因數的方式，會快很多。

輾轉相除法又稱歐幾里得演算法(Euclidean algorithm)，相信這個大家在中學階段都用得嚇嚇叫了，這邊就不再多提。簡而言之，要用輾轉相除法取得兩正整數的最大公因數，那就是把這兩數以大除小相除，取餘數後，把餘數當作原本除數的除數，再進行一次除法。取餘數後，再把這個餘數當作除數，去除前一個餘數，如此反覆，直到餘數為0時，前一個除數就是最大公因數。

程式實作如下：

pub fn gcd(mut a: i32, mut b: i32) -> i32 {
    if b > a {
        swap(&mut a, &mut b);
    }

    let mut m = a % b;

    while m != 0 {
        a = b;
        b = m;
        m = a % b;
    }

    b
}

public static int gcd(int a, int b) {
    if (b > a) {
        final int c = b;
        b= a;
        a = c;
    }

    int m = a % b;

    while(m != 0){
        a = b;
        b = m;
        m = a % b;
    }

    return b;
}

function gcd(a: number, b: number) {
    if (b > a) {
        const c = b;
        b = a;
        a = c;
    }
 
    let m = a % b;
 
    while (m !== 0) {
        a = b;
        b = m;
        m = a % b;
    }
 
    return b;
}

func Gcd(a int, b int) int {
	if b > a {
		c := b
		b = a
		a = c
	}

	m := a % b

	for m != 0 {
		a = b
		b = m
		m = a % b
	}

	return b
}

以上程式，a為被除數；b為除數；m為餘數。一開始如果b小於a，會先進行調換。採用輾轉相除法的gcd函數的時間複雜度為#{{O((\log a)(\log b))}}#。

對於不擅長處理除法的CPU，可以改用斯泰因演算法(Stein's algorithm)，又稱為二元GCD演算法(Binary GCD algorithm)。這個演算是根據以下四個事實來求最大公因數的：

若#{{a}}#和#{{b}}#是正偶數，則#{{gcd(a, b) = 2 \times gcd({a \over 2}, {b \over 2})}}#。(提取公因數#{{2}}#，最大公因數是所有公因數相乘)
若#{{a}}#是正偶數，#{{b}}#是正奇數，則#{{gcd(a, b) = gcd({a \over 2}, b)}}#。(移除#{{a}}#的質因數#{{2}}#，因為#{{2}}#不是公因數)
若#{{a}}#和#{{b}}#都是正奇數，且#{{a \gt b}}#，則#{{gcd(a, b) = gcd(a - b, b)}}#。(若我們要以減法來模擬除法，會用大數去減小數，得到差之後再去減小數，如此循環，看需要減幾次才會使得差小於等於0，所以#{{a - b}}#就是計算#{{a \over b}}#的第一步。根據輾轉相除法，我們關心的只有#{{a \over b}}#的餘數和除數，而#{{a \over b}}#和#{{ {a - b} \over b }}#，雖然商數差了1，但除數和餘數是相等的，所以可以如此替換)又因為奇數減奇數必為偶數，根據第2個事實，#{{gcd(a - b, b) = gcd({ {a - b} \over 2}, b)}}#。
若正整數#{{a}}#、#{{b}}#相等，則#{{gcd(a, b) = a}}#。

如此一來，就能將原先的輾轉相除法，變成AND(判斷奇偶)、減法、乘以2和除以2的運算。而對電腦來說，除以2或乘以2只要去右位移或是左位移一個位元就行了，所以並不需要去計算乘法和除法。根據以上列出的事實外，再另外定義：

#{{gcd(a, 0) = a}}#。(根據輾轉相除法，被當作除數的餘數為0了，就拿上一個餘數，也就是現在的被除數作為最大公因數。這只是為了方便遞迴演算法動作，不然0是不能求因數的。)
#{{gcd(0, 0) = 0}}#。(這只是為了方便遞迴演算法動作，不然0是不能求因數的。)

可以寫出以下的gcd遞迴函數：

pub fn gcd(a: usize, b: usize) -> usize {
    if a == b || b == 0 {
        a
    } else if a == 0 {
        b
    } else if a & 1 == 0 {
        if b & 1 == 0 {
            gcd(a >> 1, b >> 1) << 1
        } else {
            gcd(a >> 1, b)
        }
    } else if b & 1 == 0 {
        gcd(a, b >> 1)
    } else if a > b {
        gcd((a - b) >> 1, b)
    } else {
        gcd(a, (b - a) >> 1)
    }
}

public static int gcd(int a, int b) {
    if (a == b || b == 0) {
        return a;
    } else if (a == 0) {
        return b;
    } else if ((a & 1) == 0) {
        if ((b & 1) == 0) {
            return gcd(a >> 1, b >> 1) << 1;
        } else {
            return gcd(a >> 1, b);
        }
    } else if ((b & 1) == 0) {
        return gcd(a, b >> 1);
    } else if (a > b) {
        return gcd((a - b) >> 1, b);
    } else {
        return gcd(a, (b - a) >> 1);
    }
}

function gcd(a: number, b: number): number {
    if (a === b || b === 0) {
        return a;
    } else if (a === 0) {
        return b;
    } else if ((a & 1) === 0) {
        if ((b & 1) === 0) {
            return gcd(a >> 1, b >> 1) << 1;
        } else {
            return gcd(a >> 1, b);
        }
    } else if ((b & 1) === 0) {
        return gcd(a, b >> 1);
    } else if (a > b) {
        return gcd((a - b) >> 1, b);
    } else {
        return gcd(a, (b - a) >> 1);
    }
}

func Gcd(a int, b int) int {
	if a == b || b == 0 {
		return a
	} else if a == 0 {
		return b
	} else if a&1 == 0 {
		if b&1 == 0 {
			return Gcd(a>>1, b>>1) << 1
		} else {
			return Gcd(a>>1, b)
		}
	} else if b&1 == 0 {
		return Gcd(a, b>>1)
	} else if a > b {
		return Gcd((a-b)>>1, b)
	} else {
		return Gcd(a, (b-a)>>1)
	}
}

以迭代的方式來實作二元gcd函數：

pub fn gcd(mut a: usize, mut b: usize) -> usize {
    let mut two_counter = 0;

    loop {
        if a == b || b == 0 {
            return a << two_counter;
        } else if a == 0 {
            return b << two_counter;
        } else if a & 1 == 0 {
            a >>= 1;

            if b & 1 == 0 {
                b >>= 1;

                two_counter += 1;
            }
        } else if b & 1 == 0 {
            b >>= 1;
        } else if a > b {
            a = (a - b) >> 1;
        } else {
            b = (b - a) >> 1;
        }
    }
}

public static int gcd(int a, int b) {
    int twoCounter = 0;

    while (true) {
        if (a == b || b == 0) {
            return a << twoCounter;
        } else if (a == 0) {
            return b << twoCounter;
        } else if ((a & 1) == 0) {
            a >>= 1;

            if ((b & 1) == 0) {
                b >>= 1;

                twoCounter += 1;
            }
        } else if ((b & 1) == 0) {
            b >>= 1;
        } else if (a > b) {
            a = (a - b) >> 1;
        } else {
            b = (b - a) >> 1;
        }
    }
}

function gcd(a: number, b: number) {
    let twoCounter = 0;
 
    for (; ;) {
        if (a === b || b === 0) {
            return a << twoCounter;
        } else if (a === 0) {
            return b << twoCounter;
        } else if ((a & 1) === 0) {
            a >>= 1;
 
            if ((b & 1) === 0) {
                b >>= 1;
 
                twoCounter += 1;
            }
        } else if ((b & 1) === 0) {
            b >>= 1;
        } else if (a > b) {
            a = (a - b) >> 1;
        } else {
            b = (b - a) >> 1;
        }
    }
}

func Gcd(a int, b int) int {
	var twoCounter uint

	for {
		if a == b || b == 0 {
			return a << twoCounter
		} else if a == 0 {
			return b << twoCounter
		} else if a&1 == 0 {
			a >>= 1

			if b&1 == 0 {
				b >>= 1

				twoCounter += 1
			}
		} else if b&1 == 0 {
			b >>= 1
		} else if a > b {
			a = (a - b) >> 1
		} else {
			b = (b - a) >> 1
		}
	}
}

二元GCD演算法的時間複雜度為#{{O((log_{(2)}(a b))^2)}}#。

最小公倍數

要求兩正整數#{{a}}#、#{{b}}#的最小公倍數，只要將它們相乘，再除以它們的最大公因數就好了。

pub fn lcm(a: i32, b: i32) -> i32 {
    a * b / gcd(a, b)
}

pub fn gcd(mut a: i32, mut b: i32) -> i32 {
    if b > a {
        swap(&mut a, &mut b);
    }

    let mut m = a % b;

    while m != 0 {
        a = b;
        b = m;
        m = a % b;
    }

    b
}

public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
    
public static int gcd(int a, int b) {
    if (b > a) {
        final int c = b;
        b= a;
        a = c;
    }

    int m = a % b;

    while(m != 0){
        a = b;
        b = m;
        m = a % b;
    }

    return b;
}

function lcm(a: number, b: number) {
    return a * b / gcd(a, b);
}
 
function gcd(a: number, b: number) {
    if (b > a) {
        const c = b;
        b = a;
        a = c;
    }
 
    let m = a % b;
 
    while (m !== 0) {
        a = b;
        b = m;
        m = a % b;
    }
 
    return b;
}

func Lcm(a int, b int) int {
	return a * b / Gcd(a, b)
}

func Gcd(a int, b int) int {
	if b > a {
		c := b
		b = a
		a = c
	}

	m := a % b

	for m != 0 {
		a = b
		b = m
		m = a % b
	}

	return b
}