In the previous article "PHP Array Learning: Returning All Common Factors and the Greatest Common Factor between Given Two Numbers", we introduced a way to obtain all common factors of two integers. Factors, a method of finding the greatest common divisor. This time we will introduce to you a method of finding the greatest common divisor. Friends who are interested can learn about it~
In the previous article, we put all the factors of two integers in In two arrays, and then use the array_intersect() function to find the intersection of the two arrays, you can get an array containing all common factors; then use the max() function to calculate the maximum number in the intersection array, and you will get the greatest common factor.
Isn’t it a bit troublesome? We have to find out all the factors one by one, then calculate all the common factors, and finally find the greatest common divisor. Here's a simple and general method (can be used in other languages).
This time we do not use PHP built-in functions, but use if judgment statements and while loop statements to find the greatest common divisor between given two integers.
Implementation steps: There are two variables a and b
The first step: Make sure that large numbers are placed in a and decimals are placed in b.
This requires the use of an if statement to determine. If a
if ($a < $b) { //a < b,则交换两个数 $temp = $a; $a = $b; $b = $temp; }
Step 2: Find the remainder of a/b
, and assign the value to r
$r = $a % $b;
Step 3: Determine the remainder r Whether it is 0.
If r=0
, then b above is the greatest common divisor; if r!=0
, you need to assign the value of b to a, r Assign the value to b, continue to find the remainder of a/b, and determine whether the remainder r is 0. This requires the use of a loop (a while loop is used here):
while ($r != 0) { $a = $b; $b = $r; $r = $a % $b; }
The fourth step: output the greatest common factor b.
Let’s take a look at the implementation code:
<?php header("Content-type:text/html;charset=utf-8"); function gcd($a, $b) { $a1 = $a; $b1 = $b; if ($a < $b)//a < b,则交换两个数 { $temp = $a; $a = $b; $b = $temp; } $r = $a % $b; while ($r != 0) { $a = $b; $b = $r; $r = $a % $b; } echo "数$a1 和$b1 的最大公因数为: $b <br><br>"; } gcd(30, 40); gcd(12, 16); gcd(15, 12); ?>
Output result:
Okay, let’s talk We are here. If you want to know anything else, you can click this. → →php video tutorial
Recommended: 《PHP interview questions summary (collection)》
The above is the detailed content of PHP Loop Learning 9: Obtain the greatest common factor between two given numbers. For more information, please follow other related articles on the PHP Chinese website!