what is the Optimal solution to divide two numbers.?

general
1

What is optimal solution to find out the least number N which divides given two numbers X and Y (N!=1). Is it is possible only through loop

like


for(i=2;i<=small(X,Y),i++)
{
if(X%i==0 && Y%i==0)
break;
} 
print i;
2

for(i=2;i<a;i++)
{
if(a%i==0)
{
if(b%i==0)
break;
}
}
printf("%d",i);

3

thank you sansid. is there any direct method ? is this is the optimal solution ?

4

i think my solution and your one is same ,because Y%i computed only if X%i is true.

5

the least common divisor is a divisor of the greatest common divisor.

you could start by finding the gcd of X and Y (fast euclid), list its divisors != 1 (prime decomposition), and return the smallest one. it’s an other approach, and possibly a faster one if X and Y are both big primes, for example.

1 Like
6

you can find M=GCD(X,Y) by fast Euclid Algorithm then find the least divisor of M by following loop as 

for(i=2;i<=sqrt(M);i++)

{

if(M%i==0)

break;

}

if(i<=sqrt(M)) return i;

else return M;

and you can find the GCD by following code(Here i am assuming that X is smaller) 
GCD(X,Y)
{
while(X>0)
{ 
temp=X;
X=Y%X;
Y=temp;
}
return temp;
}
3 Likes
7

If you have a list of primes available, probably computed using some sieving algorithm, then, once you have the gcd, you can just iterate through all primes less than or equal to the square root of gcd, and check for divisibility, rather than checking 2, 3, …, sqrt(gcd).

8

In case, you do not have a list of primes, then use some optimisations like this.

First, you must know that, the least common divisor has got to be a prime (the only exception is the case 1, where the gcd is also 1). This is the prime reason, the previous optimisation worked.

Even if, we do not have a list of primes, we can cut down some numbers as follows: Except 2 and 3, all primes must be of one of the form 6k-1 or 6k+1. So, check divisibility of gcd with 2 and 3. then check divisibility by only numbers (<= sqrt(gcd)) of the form 6k-1 or 6k+1.

1 Like
9 
```

int gcd(int x, int y) /* Returns the greatest common divisor of two numbers */
{
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}

/* This function uses the idea that any common divisor of x and y must also divide
   the gcd of x and y */
int lcd(int x, int y) /* Returns the least common divisor of two numbers */
{
    int g = gcd(x, y);
    if (g == 1) /* Base Case */
        return 1;
    else if (g % 2 == 0) /* Base Case */
        return 2;
    else if (g % 3 == 0) /* Base Case */
        return 3;
    else
    {
        int j, sq;
        sq = (int) sqrt(g);
        for (j = 6; j - 1 <= sq; j += 6) /* Checking only with possible primes */
        {
            if (g % (j - 1)) == 0)
                return j + 1;
            else if ((j + 1 <= sq) && (g % (j + 1) == 0))
                return j + 1;
        }
        return g;
    }
}
10

i am just giving the view to solve the problem it is up to you that how can you optimize that …

11

thank you i got the idea.

12

i got the idea thank you, I think idea of dividing M by 6k-1 or 6k+1 will improve speed as suggested by tijoforyou . is it the optimal solution. is there any method to find prime directly…

13

Check your gcd() function. You have forgot to write something.

14

:stuck_out_tongue: yup, i mis-wrote the gcd. Thak you for the point.
Edited! :slight_smile:

15

@maheshksd to get to the primes directly, you need to have some sieving techniques implemented. Check out http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes to get more details on the simplest sieving algorithm.
Then, you will have a list of primes available with you, and you can iterate over the list directly.

16

thanks you very much…