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.

  • $\begingroup$ This does not work everytime but if $a$ and $b$ are coprime, $\text{lcm}(a,b)=ab$ $\endgroup$ – Mohammad Zuhair Khan Oct 27 '18 at 12:25
  • $\begingroup$ @Raptor, just edited the question. $\endgroup$ – Maged Saeed Oct 27 '18 at 12:28
  • $\begingroup$ 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$? $\endgroup$ – Arthur Oct 27 '18 at 12:30
  • 3
    $\begingroup$ No, since gcd & lcm can be computed from each other by cancelling the other from $ab$ they have the same computational complexity in general. $\endgroup$ – Bill Dubuque Oct 27 '18 at 13:05
  • 1
    $\begingroup$ Also, at most $\log n$ is pretty fast. Converting base $10$ to base $2$ is $\log n$ divisions. $\endgroup$ – Aaron Meyerowitz Nov 2 '18 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.