A very easy question though, yet thought posting about it thinking it may improve my explanation prowess.
Lets get back to old school math, how did we find Greatest Common Divisor (GCD) or you may call it Highest Common Factor(HCF) of two numbers?
Assuming you know primary Maths, I'd proceed further.
Lets take an example before we go ahead.
Find GCD of 54 and 24.
Divisors of 54 are: 1, 2, 3, 6, 9, 18, 27, 54.
Divisors of 24 are: 1, 2, 3, 4, 6, 8, 12, 24.
Common divisors of 54 and 24: 1, 2, 3, 6
The greatest of these is 6.
Hence gcd(54,24) = 6
Okay, lets write an algorithm for this. Well, one would say, there's nothing to think of any algorithm, things are crystal clear. Find out the factors of two numbers, then find common factors and then the largest of them.
But brother! There exists a better algorithm. Our Father of Geometry, Euclid, left us an algorithm already. We simply have to implement it.
Lets see how it works.
We are given two numbers, 54 and 24
Lets call a = 54 and b = 24
1. Store current value of a in some temporary variable.
temp = a
2. Store remainder when b is divided by a in a.
a = b mod a OR a = b % a //yeah, % is used to get remainder
3. Store the previous value of a in b. Oh but we lost a in step 2 :-o . Yeah, that's why we used temp to record previous a's value.
b = temp
Continue this process until a becomes 0, you'll be left with Greatest Common Divisor of two numbers in variable b.
That's it people, that's all for the show ;-) Let's jump into coding.
C/C++ Code Snippet for gcd of two numbers.
I've introduced a little variation in Python code so that we don't have to use temp variable.
Line #3: yeah, we can directly assign older value of a to b just like that using comma ',' operator in one statement. Python users will know it.
Oh, almost forgot, we can also do it using Python in-built library too.
Okay this was just for two numbers, How would you do it for a list of numbers i.e. an array of integers.
Simple enough! Iterate over the list or array.
If you have [4,6,14,10], we can cut it down like this:
gcd(4,6) = 2, now we have [2,14,10]
gcd(2,14) = 2, now we have [2,10]
gcd(2,10) = 2, now we have [2], hence our answer is 2.
Here's is a generalized method in C/C++ to do it.
This becomes a hell lot easier if you certain built-in functions in Python. reduce(FUNCTION_NAME, LIST) is one such function.
Its job is as follows:
if we say reduce(gcd,[4,6,14,10]) it will think of it as such a form
gcd(gcd(gcd(4,6),14),10)
Note: Comment out line #3 and Comment line #2 in order to take input from user.
Hope you guys kind of get it.
Got a burning question you wanna get answered. Ask it in the comments or leave a message at our Facebook Page.
Lets get back to old school math, how did we find Greatest Common Divisor (GCD) or you may call it Highest Common Factor(HCF) of two numbers?
Assuming you know primary Maths, I'd proceed further.
Lets take an example before we go ahead.
Find GCD of 54 and 24.
Divisors of 54 are: 1, 2, 3, 6, 9, 18, 27, 54.
Divisors of 24 are: 1, 2, 3, 4, 6, 8, 12, 24.
Common divisors of 54 and 24: 1, 2, 3, 6
The greatest of these is 6.
Hence gcd(54,24) = 6
Okay, lets write an algorithm for this. Well, one would say, there's nothing to think of any algorithm, things are crystal clear. Find out the factors of two numbers, then find common factors and then the largest of them.
But brother! There exists a better algorithm. Our Father of Geometry, Euclid, left us an algorithm already. We simply have to implement it.
Lets see how it works.
We are given two numbers, 54 and 24
Lets call a = 54 and b = 24
1. Store current value of a in some temporary variable.
temp = a
2. Store remainder when b is divided by a in a.
a = b mod a OR a = b % a //yeah, % is used to get remainder
3. Store the previous value of a in b. Oh but we lost a in step 2 :-o . Yeah, that's why we used temp to record previous a's value.
b = temp
Continue this process until a becomes 0, you'll be left with Greatest Common Divisor of two numbers in variable b.
That's it people, that's all for the show ;-) Let's jump into coding.
C/C++ Code Snippet for gcd of two numbers.
I've introduced a little variation in Python code so that we don't have to use temp variable.
Line #3: yeah, we can directly assign older value of a to b just like that using comma ',' operator in one statement. Python users will know it.
Oh, almost forgot, we can also do it using Python in-built library too.
Okay this was just for two numbers, How would you do it for a list of numbers i.e. an array of integers.
Simple enough! Iterate over the list or array.
If you have [4,6,14,10], we can cut it down like this:
gcd(4,6) = 2, now we have [2,14,10]
gcd(2,14) = 2, now we have [2,10]
gcd(2,10) = 2, now we have [2], hence our answer is 2.
Here's is a generalized method in C/C++ to do it.
This becomes a hell lot easier if you certain built-in functions in Python. reduce(FUNCTION_NAME, LIST) is one such function.
Its job is as follows:
if we say reduce(gcd,[4,6,14,10]) it will think of it as such a form
gcd(gcd(gcd(4,6),14),10)
Note: Comment out line #3 and Comment line #2 in order to take input from user.
Hope you guys kind of get it.
Got a burning question you wanna get answered. Ask it in the comments or leave a message at our Facebook Page.
