least common divisors

Question

what i am trying is write recursive function which return least common divisor or for example let take let take 150 and 125 greatest common divisor is 25 while least common divisor is 5 once again i need recurive fucntion in direct method it is trivial

Answer 1

Test every number until sqrt(min(a, b)): if the numbers are both divisible by it, you found it. You can only test primes if you want.

If you haven't found any such number, then check if the other number is a multiple of the minimum: if yes, the minimum of the two is the solution. Otherwise, there's no solution.

You can do better. You can go only up to sqrt(gcd(a, b)). That should be fast enough.