Algorithms : complete 01-algorithmic_toolbox 01-intro

1 files changed, 31 insertions, 3 deletions

diff --git a/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp b/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp
index c6f503c..62e7799 100644
--- a/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp
+++ b/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp
@@ -1,8 +1,36 @@
 #include <iostream>
 
-long long lcm(int a, int b) {
-  //write your code here
-  return a*b;
+long long gcd(int a, int b)
+{
+    long long d, r;
+
+    if ((a == b) || (a == 0))
+        return a;
+
+    if (b == 0)
+        return b;
+
+    if (b > a) {
+        d = a;
+        a = b;
+        b = d;
+    }
+
+    for(;;) {
+        d = a / b;
+        r = a - (d * b);
+        if (r == 0)
+            break;
+        a = b;
+        b = r;
+    }
+
+    return (long long) b;
+}
+
+long long lcm(int a, int b)
+{
+    return (b / gcd(a, b)) * a;
 }
 
 int main() {