bigkm1 at gmail dot com ¶
18 年前
(PHP 4 >= 4.0.4, PHP 5, PHP 7, PHP 8)
gmp_gcd — 計算最大公因數
計算 num1 和 num2 的最大公因數。即使其中一個或兩個輸入運算元為負數，結果也始終為正數。
num1一個 GMP 物件、一個 int 或一個可被解釋為數字的 string，其邏輯與在 gmp_init() 中使用字串並自動偵測基數（即 base 等於 0 時）相同。
num2一個 GMP 物件、一個 int 或一個可被解釋為數字的 string，其邏輯與在 gmp_init() 中使用字串並自動偵測基數（即 base 等於 0 時）相同。
base 等於 0 時）相同。返回值
num1 和 num2 的正 GMP 數。
範例
範例 #1 gmp_gcd() 範例<?php
$gcd = gmp_gcd("12", "21");
echo gmp_strval($gcd) . "\n";
?>
3
limas at kultur-online dot at ¶
17 年前
{
先前的函式在 php 5.2.4 下只返回 1，但以下函式似乎可以運作 (m>0,n>0)
function gcd($m,$n)
$_m=$m;$r=1;
{
if($m<$n){$t=$m;$m=$n;$n=$t;}
while($r)
}
$r=(floor($m/$n)*$n)-$m;
} Ludwig Heymbeeck ¶
函式 GCD($num1, $num2) {
/* 找出兩數的最大公因數 */
while ($num2 != 0) {
$t = $num1 % $num2;
$num1 = $num2;
$num2 = $t;
}
return $num1;
}這是我的解法，用於取得多個數字的最大公因數。
<?php
/*
* 函式 gcd()
*
* 傳回兩數的最大公因數
* 已與 gmp_gcd() 進行測試
*/
function gcd($a, $b)
{
if ($a == 0 || $b == 0)
return abs( max(abs($a), abs($b)) );
$r = $a % $b;
return ($r != 0) ?
gcd($b, $r) :
abs($b);
}
/*
* 函式 gcd_array()
*
* 取得陣列中多個數字的最大公因數
*/
function gcd_array($array, $a = 0)
{
$b = array_pop($array);
return ($b === null) ?
(int)$a :
gcd_array($array, gcd($a, $b));
}
?>我想要這個功能，但又不想安裝擴充套件。
所以這是我寫的用於找出最大公因數的程式碼
<?php
// 我們的分數 3/12 可以更簡潔地表示
$numerator = 3;
$denominator = 12;
/**
* @param int $num
* @return array $num 的公因數
*/
function getFactors($num)
{
$factors = [];
// 取得分子的因數
for ($x = 1; $x <= $num; $x ++) {
if ($num % $x == 0) {
$factors[] = $x;
}
}
return $factors;
}
/**
* @param int $x
* @param int $y
*/
function getGreatestCommonDenominator($x, $y)
{
// 首先取得分子和分母的公因數
$factorsX = getFactors($x);
$factorsY = getFactors($y);
// 公因數會同時存在兩個陣列中，因此取得交集
$commonDenominators = array_intersect($factorsX, $factorsY);
// 最大公因數是陣列中最大的數字（最後一個元素）
$gcd = array_pop($commonDenominators);
return $gcd;
}
// 將分子和分母除以最大公因數，得到簡化後的分數
$gcd = getGreatestCommonDenominator($numerator, $denominator);
echo ($numerator / $gcd) .'/'. ($denominator / $gcd); // 我們可以使用除法 (/)，因為我們知道結果是整數 :-)
您可以在這裡看到程式碼執行結果 https://3v4l.org/uTucY如果您不考慮 a 或 b 為負數的情況，GCD 函數可能會返回負的 GCD，這並非最大公因數，因此像這樣的函數可能會更好。這考慮了 (-3)-(-6) 的簡化，其中 -3 和 -6 的 gcd 結果為 3，而不是像其他函數那樣得到 -3。(-3)-(-6) 是 (-1)-(-2) 而不是 (1)-(2)
function eGCD($a,$b){
if($a < 0) $a=0-$a;
if($b < 0 ) $b=0-$b;
if($a == 0 || $b == 0) return 1;
if($a == $b) return $a;
do{
$rest=(int) $a % $b; $a=$b; $b=$rest;
}while($rest >0);
return $a;
}不需要僅為了 GCD 函數而編譯 gmp 函數... 使用這個函數代替
函式 GCD($num1, $num2) {
/* 找出兩數的最大公因數 */
if ($num1 < $num2) {
$t = $num1;
$num1 = $num2;
$num2 = $t;
}
while ($t = ($num1 % $num2) != 0) {
$num1 = $num2;
$num2 = $t;
}
return $num2;
}function gcd($a,$b)
{
return $b ? gcd($b, $a%$b) : $a;
}
這個程式碼簡潔快速，也容易記住。如果 $b 為零，則返回 a，否則交換並取餘數。