CODEWITHSUNDEEP
algorithm
user466534
user466534

Reputation:

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 direct method it is trivial.

Upvotes: 0

Views: 2184

Answers (3)

Saurabh
Saurabh

Reputation: 7833

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

Upvotes: 0

nikoo28
nikoo28

Reputation: 2971

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

Upvotes: 1

IVlad
IVlad

Reputation: 43477

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.

Upvotes: 2

Related Questions