Program to find GCD of two integers using Euclid’s Algorithm

 

Program to find GCD of two integers using Euclid’s Algorithm

ALGORITHM :

Step 1: Start Step 2: Input the two integers (num1 and num2). Step 3: Repeat the following steps until num2 is not equal to 0: a. Calculate the remainder (rem) of num1 divided by num2. b. Set num1 to num2. c. Set num2 to rem. Step 4: The GCD of the original two integers is stored in num1. Step 5: Display the GCD. Step 6: End

SOURCE CODE :

#include<stdio.h>

int gcd(int, int);

int main()

{

    int num1, num2;

    printf("Enter 2 positive integer numbers\n");

    scanf("%d%d", &num1, &num2);

    printf("\nGCD of %d and %d is %d.\n", num1, num2, gcd(num1, num2));

    return 0;

}

int gcd(int n1, int n2)

{

    if(n1 == 0) return n2;

    if(n2 == 0) return n1;

    if(n1 > n2)

        return gcd(n1%n2, n2);

    else

        return gcd(n1, n2%n1);

}

OUTPUT :