least common divisors

What I am trying is write recursive function which returns the least common divisor or for example let's take 150 and 125, the greatest common divisor is 25 while the least common divisor is 5. Once again I need a recursive function in dire开发者_运维百科ct method it is trivial.

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.

if you want to find the least common factor of an array elements, you can first compute the GCD of all the elements and then find the least prime factor of the GCD obtained...

to get the gcd of all array elements:-

g=arr[0];
for(i=1;i<arr.length();i++)
   g=gcd(g,arr[i]);

now, to get the least prime factor loop till sqrt(g)

for(i=2;i<=sqrt(g);i++)
  if(g%i==0)
    return g

Python implementation:
Above solution will not work for this numbers 5 and 10 where least common divisor is 5 so taking square root wont work here

from math import gcd
def leastCommonPrimeDivisor(a, b):
    g=gcd(a,b)  # gcd of a and b
    for i in range(2,g+1):
        if g%i==0:
            return i # returns least common divisor
    return -1