#!/usr/bin/env python
# coding: utf-8

# # Μέγιστος Κοινός Διαιρέτης και Ελάχιστο Κοινό Πολλαπλάσιο

# Έστω ένα ορθογώνιο διαστάσεων x=30cm, y=12cm. Να βρεθεί ο μικρότερος αριθμός από τετράγωνα (ακέραιας πλευράς) που το καλύπτει.

# Απάντηση: ΜΚΔ(30,12) = 6

# In[1]:


# μια απλοϊκή υλοποίηση
def gcd_naive(x, y):
    z = min(x, y)
    for i in range(z, 0, -1):
        if x % i == 0 and y % i == 0:
            return i


# In[2]:


# τυχαίες ακέραιες τιμές σε ένα διάστημα
import random

random.randrange(5000, 20000)


# In[10]:


get_ipython().run_cell_magic('timeit', '', '# χρονομέτρηση απλοϊκού αλγορίθμου εύρεσης ΜΚΔ\n\na = random.randrange(50000, 200000)\nb = random.randrange(50000, 200000)\nx = gcd_naive(a,b)\n')


# In[4]:


# ταχύτερος αλγόριθμος (αλγόριθμος του Ευκλείδη)
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


# In[11]:


get_ipython().run_cell_magic('timeit', '', '\na = random.randrange(50000, 200000)\nb = random.randrange(50000, 200000)\n\nx = gcd(a,b)\n')


# ### Αλγόριθμος του Ευκλείδη για την εύρεση του ΜΚΔ
# 
# Πολυπλοκότητα: $\mathcal{O}(\log{(min(x,y))})$ 
# 
# https://www.baeldung.com/cs/euclid-time-complexity

# In[6]:


# Ελάχιστο κοινό πολλαπλάσιο


def lcm(x, y):
    return x * y / gcd(x, y)


a, b = 30, 12
print(gcd(a, b), lcm(a, b))