4
$\begingroup$

I am not understanding how the following formular works

http://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm

Actually what I did (for my programming homework was loop through the max of 2 numbers until I get 1 that divides both given numbers without a remainder). Bruteforce, so not ideal. So I want to understand more about this formular instead of just using it.

public static int gcd(int a, int b) {   /**    * Get max of both numbers    * Loop down max number and test if its divisible by both numbers    * if yes, thats the answer, else continue    * if no answer, return 0    */   int max = Math.max(a, b);   for (int i = max; i > 0; i--) {     if (a % i == 0 && b % i ==0) {       return i;     }   }   return 0; } 
  • 0
    Note that the comment says exactly what the loop does. (`a % i` takes the remainder after dividing `a` by `i`.)2011-08-23
  • 1
    Note that the [Euclidean algorithm article on Wikipedia](http://en.wikipedia.org/wiki/Euclidean_algorithm) gives a few better implementations...2011-08-23
  • 0
    @J.M. I am new to this site and not a maths person so I'm not sure what other tags should I put. I know the formula works. I know % or mod is the remainder. But I do not understand why after recursively dividing the quotient with the remainder (of the prev iteration) will give the gcd of 2 numbers. Hope you get what I mean2011-08-23
  • 0
    I will take a look at the article soon, gtg to next lesson2011-08-23
  • 0
    After peering closely at the code... you could have started with the *minimum* instead of the maximum; $a$ can't be divisible by $b$ is $b$ is bigger, no? The "Description" portion of the wiki-article explains Euclid's idea.2011-08-23
  • 0
    @J. M.:As Implementation I always find `int gcd(int a int b){return b?gcd(b,a%b):a;}` to be fairly simple and smooth :-)2011-08-23
  • 0
    @Fool: yes, if the environment supports recursion. If not, then some elaboration is necessary...2011-08-23
  • 0
    @jiewmeng:There is nothing much to understand unless you meant to a formal proof,it is the same old way we are taught to do find H.C.F or G.C.D since elementary.2011-08-23
  • 0
    @J.M:Umm..do you know about any *modern* environment that do not support recursion?2011-08-23
  • 0
    With the adjective *modern* @Fool, I can't think of any. On the other hand, people do still write for legacy systems... but we are already off-topic here.2011-08-23
  • 0
    Isn't it just pure brute-force, hardly an algo. then in terms of efficiency.2017-12-02

4 Answers 4