# Any faster algorithm to find the least common multiple?

To find the least common multiple of $$a,b$$, call it $$\operatorname{lcm}(a,b)$$, divide there product by there greatest common divisor. However, finding the gcd requires at most $$\log n$$ time. I am wondering if there is a faster algorithm than so.

• This does not work everytime but if $a$ and $b$ are coprime, $\text{lcm}(a,b)=ab$ – Mohammad Zuhair Khan Oct 27 '18 at 12:25
• @Raptor, just edited the question. – Maged Saeed Oct 27 '18 at 12:28
• Almost any arithmetic calculation using $a$ and $b$ will require $\log n$ time (assuming $n=\min(a,b)$). What makes you think the lcm is significantly faster than, say, the sum $a+b$? – Arthur Oct 27 '18 at 12:30
• No, since gcd & lcm can be computed from each other by cancelling the other from $ab$ they have the same computational complexity in general. – Bill Dubuque Oct 27 '18 at 13:05
• Also, at most $\log n$ is pretty fast. Converting base $10$ to base $2$ is $\log n$ divisions. – Aaron Meyerowitz Nov 2 '18 at 20:41