Algorithms : complete 01-algorithmic_toolbox 01-intro

1 files changed, 25 insertions, 10 deletions

diff --git a/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp b/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp
index f723be2..fc13392 100644
--- a/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp
+++ b/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp
@@ -1,16 +1,31 @@
 #include <iostream>
 
-int gcd(int a, int b) {
-  //write your code here
-  int current_gcd = 1;
-  for (int d = 2; d <= a && d <= b; d++) {
-    if (a % d == 0 && b % d == 0) {
-      if (d > current_gcd) {
-        current_gcd = d;
-      }
+int gcd(int a, int b)
+{
+    int d, r;
+
+    if ((a == b) || (a == 0))
+        return a;
+
+    if (b == 0)
+        return b;
+
+    if (b > a) {
+        d = a;
+        a = b;
+        b = d;
     }
-  }
-  return current_gcd;
+
+    for(;;) {
+        d = a / b;
+        r = a - (d * b);
+        if (r == 0)
+            break;
+        a = b;
+        b = r;
+    }
+
+    return b;
 }
 
 int main() {