A program to compute H.C.F. (also called G.C.D.) and L.C.M. of any two numbers is something which most of the programmers write at very early stage of learning a programming language and is considered a trivial programming task. Most of us follow the basic way by iterating through a range of numbers and checking them for a factor or a multiple and hence computing the desired result. This approach is easy to code but results in an extremely slow program, when dealing with big numbers. In this post I am going to mention about an algorithm which is much faster and easy to code too.
First let's start with computation of H.C.F. for any two numbers. The very first step is to divide the larger number by the smaller number, and then if the remainder obtained is a non-zero value, then divide the divisor (the smaller number in this case) with the obtained remainder (remainder will become the new divisor in this second division). Keep repeating this procedure of dividing the divisor of every division with the obtained remainder, until your obtained reminder becomes zero. Then the last divisor in your last division (the one with zero remainder), is the required H.C.F. value.
NOTE: In a/b, 'a' is the dividend (numerator) and 'b' is the divisor (denominator).
For example, if we want to compute H.C.F. for any two numbers, lets say 1651 and 2032,
As 2032 > 1651, so we will start by dividing 2032 by 1651
NOTE: '%' is symbol for modulus i.e. a%b = remainder obtained on dividing a by b (remainder of a/b).
2032 % 1651 = 381 (381 is the remainder obtained in dividing 2032 by 1651)
1651 % 381 = 127 (1651 was our last divisor, 381 was remainder obtained in last division and 127 is our new obtained remainder)
381 % 127 = 0 (Now we have obtained a zero remainder so we will stop here)
Our last obtained divisor is 127, and is the H.C.F. of 1651 and 2032.
Now, for H.C.F. of three numbers (a,b,c) = HCF(HCF(a,b),c) [here, HCF(a.b) means H.C.F. value of a and b], and in the similar way we can easily obtain H.C.F. of more than three numbers.
Now I am going to state a better way to obtain L.C.M. of any two numbers, although the technique I mentioned above to compute H.C.F. can be used to compute H.C.F. for more than two numbers too, but the technique to compute L.C.M. which I am going to mention is only limited to two numbers ONLY.
In computation of L.C.M. of two numbers we are going to make use of above mentioned H.C.F. of two numbers technique and going to take advantage of the property -
Product of any TWO numbers = Product of their H.C.F. and L.C.M.
i.e. for any TWO numbers a,b
a*b = [H.C.F. of (a,b)] * [L.C.M. of (a,b)]
hence, L.C.M. of (a,b) = (a*b) / [H.C.F of (a,b)]
Hence using this property, now we can easily compute H.C.F. and L.C.M. of any two numbers in a faster and efficient way.
First let's start with computation of H.C.F. for any two numbers. The very first step is to divide the larger number by the smaller number, and then if the remainder obtained is a non-zero value, then divide the divisor (the smaller number in this case) with the obtained remainder (remainder will become the new divisor in this second division). Keep repeating this procedure of dividing the divisor of every division with the obtained remainder, until your obtained reminder becomes zero. Then the last divisor in your last division (the one with zero remainder), is the required H.C.F. value.
NOTE: In a/b, 'a' is the dividend (numerator) and 'b' is the divisor (denominator).
For example, if we want to compute H.C.F. for any two numbers, lets say 1651 and 2032,
As 2032 > 1651, so we will start by dividing 2032 by 1651
NOTE: '%' is symbol for modulus i.e. a%b = remainder obtained on dividing a by b (remainder of a/b).
2032 % 1651 = 381 (381 is the remainder obtained in dividing 2032 by 1651)
1651 % 381 = 127 (1651 was our last divisor, 381 was remainder obtained in last division and 127 is our new obtained remainder)
381 % 127 = 0 (Now we have obtained a zero remainder so we will stop here)
Our last obtained divisor is 127, and is the H.C.F. of 1651 and 2032.
Now, for H.C.F. of three numbers (a,b,c) = HCF(HCF(a,b),c) [here, HCF(a.b) means H.C.F. value of a and b], and in the similar way we can easily obtain H.C.F. of more than three numbers.
Now I am going to state a better way to obtain L.C.M. of any two numbers, although the technique I mentioned above to compute H.C.F. can be used to compute H.C.F. for more than two numbers too, but the technique to compute L.C.M. which I am going to mention is only limited to two numbers ONLY.
In computation of L.C.M. of two numbers we are going to make use of above mentioned H.C.F. of two numbers technique and going to take advantage of the property -
Product of any TWO numbers = Product of their H.C.F. and L.C.M.
i.e. for any TWO numbers a,b
a*b = [H.C.F. of (a,b)] * [L.C.M. of (a,b)]
hence, L.C.M. of (a,b) = (a*b) / [H.C.F of (a,b)]
Hence using this property, now we can easily compute H.C.F. and L.C.M. of any two numbers in a faster and efficient way.
No comments:
Post a Comment