Greatest Common Divisor (GCD) : Faktor Persekutuan Terbesar

Faktor pembagi terbesar (FPB) is the largest bialangan positive integers that can divide up the two numbers. To find the gcd can use a simple way (factor trees), factorial and the Euclidean algorithm.

How to determine the FPB is to look at factors such numbers and using prime factorization. Which he takes the rank is the lowest rank.

Example :

Find the gcd of 6 and 8 by looking at the factors in these numbers!

Factor of 20 = {1, 2, 3}
Factor of 30 = {1, 2⁴}

Thus, the gcd of 6 and 8 is 2

Now we can make the algorithm to make the program determines the gcd of two numbers are entered. Suppose we inputkan m and n. m and n are not negative integers. To find the FPB we must determine the greatest value, for example (m> = n), then the algorithm to find gcd ( algoritma Euclidean) are as follows (with pseudocode):

1.         If n = 0 then m is gcd (m, n), but if n ≠ 0 go to step 2.

2.         Divide m by n and let r be the remainder.

3.         Change the value of m with a value of n and n values ​​with the values ​​of r, and then reset back to step 1.

To perform the third step we can use goto.

Examples of the program as follows

For more details please take here FREE!