您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 相關知識

PHP 計算兩個整數最大公約數的三種經典算法實現

編輯：PHP 相關知識

在 PHP 開發中，計算兩個整數的最大公約數（GCD）是一個常見的數學運算需求。本文將詳細介紹三種經典的實現方法，包括歐幾里得算法、基於定義的暴力枚舉法以及質因數分解法，並附帶完整的代碼示例與性能對比，幫助開發者根據實際場景選擇最優方案。

一、歐幾里得算法（輾轉相除法）

這是計算最大公約數最高效、最經典的算法，時間複雜度為 O(log min(m,n))。核心思想是：兩個整數的最大公約數等於其中較小的數和兩數相除餘數的最大公約數。

<?php
function gcdEuclidean($m, $n) {
    // 處理邊界情況
    if ($m == 0 && $n == 0) return false;
    if ($n == 0) return $m;
    
    // 核心遞邏：不斷用除數替換被除數，餘數替換除數
    while ($n != 0) {
        $r = $m % $n;
        $m = $n;
        $n = $r;
    }
    return $m;
}

優點：效率極高、代碼簡潔、適用於大數計算。
缺點：對於初學者，數學原理可能不夠直觀。

二、基於定義的暴力枚舉法

直接根據最大公約數的定義，從兩數中較小者開始向下遍歷，找到第一個能同時整除兩數的數即為結果。時間複雜度 O(min(m,n))。

<?php
function gcdByDefinition($m, $n) {
    if ($m == 0 && $n == 0) return false;
    $min = min($m, $n);
    while ($min >= 1) {
        if ($m % $min == 0 && $n % $min == 0) {
            return $min;
        }
        $min--;
    }
    return $min;
}

優點：邏輯直觀，易於理解和實現。
缺點：當數值較大時效率極低，不適合生產環境使用。

三、質因數分解法（中學數學方法）

將兩數分解為質因數的乘積，取公共質因數中指數最小者相乘。雖然思想經典，但實現較為複雜，需要先獲取質數表（通常使用埃拉托斯特尼篩法）。

<?php
function gcdByPrimeFactorization($m, $n) {
    // 獲取質數列表（埃拉托斯特尼篩法）
    function getPrimes($num) {
        $sieve = range(2, $num);
        for ($i = 2; $i <= sqrt($num); $i++) {
            if ($sieve[$i - 2] != 0) {
                for ($j = $i * $i; $j <= $num; $j += $i) {
                    $sieve[$j - 2] = 0;
                }
            }
        }
        return array_filter($sieve);
    }
    
    // 分解質因數
    function getPrimeFactors($num, $primes) {
        $factors = [];
        foreach ($primes as $p) {
            while ($num % $p == 0) {
                $factors[] = $p;
                $num /= $p;
            }
            if ($num == 1) break;
        }
        return $factors;
    }
    
    $primes = getPrimes(max($m, $n));
    $mFactors = getPrimeFactors($m, $primes);
    $nFactors = getPrimeFactors($n, $primes);
    
    // 取交集並計算最小指數乘積
    $common = array_intersect($mFactors, $nFactors);
    $result = 1;
    foreach (array_count_values($common) as $factor => $count) {
        $mCount = array_count_values($mFactors)[$factor] ?? 0;
        $nCount = array_count_values($nFactors)[$factor] ?? 0;
        $result *= pow($factor, min($mCount, $nCount));
    }
    return $result;
}

優點：數學原理清晰，適合教學演示。
缺點：實現複雜、效率較低、大數分解質因數極其耗時。