What is the easiest way to find the greatest common factors of two integers?
#83172. Asked by Alsoco. (Jul 10 07 6:49 PM)
If either number is negative, drop its negative sign. |
If 'a' is smaller than 'b', then swap them so 'a' is greater than or equal to 'b'. This step is not strictly necessary, but it will help avoid one division step below.
If 'b' is zero, then the greatest common divisor is 'a'. We are now done. But...
If 'b' is not zero, then divide 'a' by 'b' and get the remainder.
Go back to step 3, using 'b' as the new 'a' value and the remainder from step 4 as the new 'b' value.
I don't know whether this is the easiest. But basically what we need to do is take the "prime factorization" of the number.|
Prime factorization is basically : expressing a number as a product of prime numbers such as 2, 3, 5, 7, and so on.
So if I were to find the GCF of say 14, 28 and 42
Then the prime factorization of each of these numbers gives:
14 = 7 x 2
28 = 7 x 2 x 2
42 = 7 x 3 x 2
Taking a good look now at the factors of the thress numbers, you find that they all have one '7' and one '2' in common.
To find the GCF: You need to multiply the common factors (in this case 7 and 2)
So you get: GCF of 14, 28 and 42 is 7 x 2 = 14
The link below also gives a good example(s)
Find something useful here? Please help us spread the word about FunTrivia. Recommend this page below!