CODEWITHSUNDEEP
calgorithm
user13812739
user13812739

Reputation:

Calculating GCD using Euclid's algorithm

I was reading about Euclid's algorithm to calculate GCD and found the following code:

#include <stdio.h> 
int main() 
{
    int m, n;
    scanf("%d%d", &n, &m);
    if (n < 0) n = -n;
    if (m < 0) m = -m;
    while(n != 0) 
    {   
        int temp = n;
        n = m % n; 
        m = temp;
    }
    if(m != 0)
        printf("The gcd is %d\n", m);
    return 0; 
}

But I have some questions:

  1. why if n<0 or m<0 we let n=-n or m=-m

  2. What if m==0 what should I return? The smallest possible GCD is 1 but this function doesn't return anything in this case... (If we ignore return 0 which is necessary for main)

Upvotes: 0

Views: 440

Answers (2)

Henry
Henry

Reputation: 43758

The second part of the algorithm only works for non-negative values of m and n. Since gcd(m,n) = gcd(|m|,|n|) they are made positive.

If m = 0 and n != 0 the gcd is n and vica versa.

If both n and m are 0 the gcd is undefined because every number is a divisor of 0. Therefore, nothing is printed in this case.

Upvotes: 2

Benjamin
Benjamin

Reputation: 3448

Answer 1:

This algorithm works properly for the non-negative value m and positive value n.

Example:

GCD(-6, 2) = GCD(6, -2) = GCD(-6, -2) = GCD(6, 2) = 2

Answer 2:

If m == 0 then this function will return GCD equal n

Upvotes: 1

Related Questions