It's time to publish the most optimal solution for finding the greatest divisor (GCD) and the least common multiple (LCM).
Maybe the solution looks a bit of messy but I'll update the page and clarify everything ASAP.
Greatest Common Divisor
import math as math import random as random import sys as sys sys.setrecursionlimit(1000000000)
def EuclidGCD(a, b): if b == 0: return a return EuclidGCD(b, a % b)
def stressTest(): # Stress Test while True: randOne = random.randrange( 100000, 100000000000000000000000000000000000000000) randTwo = random.randrange( 100000, 100000000000000000000000000000000000000000) print(randOne) print(randTwo) Niev = math.gcd(randOne, randTwo) fast = EuclidGCD(randOne, randTwo) print("Fast GCD: ", fast) print("Niev GCD: ", Niev) if fast != Niev: break
def main(): a = int(input()) b = int(input()) print("GCD of A and B: ", EuclidGCD(a, b))
if __name__ == "__main__": main()
Least Common Multiple
# Instead of rewriting, here we imported # our previously created GCD algorithm import GCD as GCD def GetLcm(a, b): return int(a*b/GCD.EuclidGCD(a, b)) print(GetLcm(21, 6))