Category Archives: GCD

GCD Greatest Common Divisor(Factor)/Highest Common Factor

এখানে লজিকটা হচ্ছে…Here the logic is:
For 12:
1×12=12
2×6=12
3×4=12
So factor of 12=1,2,3,4,6,12
(We don’t need the negative values here)

For 30:
1×30=30
2×15=30
3×10=30
5×6=30
So factor of 30=1,2,3,5,6,10,15,30

Now which is the common factor among 12 and 30
So factor of 12=1,2,3,4,6,12
So factor of 30=1,2,3,5,6,10,15,30

common factor=1,2,3,6
Largest common factor here=6

So now if we divide 12/6 then we get 2
and for 30/6 we get 5

that is all divided perfectly so the logic should be like this

1.Find all the factors of each number
2. Circle the common factors
3. Choose the greatest of those
4. Divide the existing number with greatest common factor thern also get a perfect divide

Here is my code:

gcd

Here is a link that described many thinks about this clearly: http://www.mathsisfun.com/greatest-common-factor.html

 

Another method can also apply here:
link for understanding the modarithmetic euclidean algorithmhttps://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

Code: