PHP Loop Learning 9: Obtain the greatest common factor between two given numbers

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!