How To Find GCD of Two Numbers In C Program

 

1. C Program to Find GCD of Two Numbers Using For loop

In this program, the compiler will ask the user to enter the two numbers that the user wants to find it’s GCD. After the user enters the program start executing and prints the output on the screen.

C

1

#include<stdio.h>

2

void main()

3

{

4

    int n1,n2,i,min,GCD;

5

    printf("Enter two integers to find their GCD: \n ");

6

    scanf("%d%d",&n1,&n2);

7

    min = (n1<n2)?n1:n2;

8

    for(i=1;i<=min;i++)

9

    {

10

        // Checks if i is factor of n1 &n2 

11

        if(n1%i==0 && n2%i==0)

12

        {

13

            GCD = i;

14

        }

15

    }

16

    printf("\n G.C.D of %d and %d is %d", n1, n2, GCD);

17

}

Output:

Explanation:

1st Iteration: for(i=1;i<=min;i++) i.e for(i=1;1<=4;i++) and if(n1%i==0 && n2%i==0) i.e (4%1==0 && 6%1==0) is TRUE then the value of GCD becomes 1 i.e GCD=1.

2nd Iteration: for(i=2;i<=min;i++) i.e for(i=2;2<=4;i++) and if(n1%i==0 && n2%i==0) i.e (4%2==0 && 6%2==0) is TRUE then the value of GCD becomes 2 i.e GCD=2.

3rd Iteration: for(i=3;i<=min;i++) i.e for(i=3;3<=4;i++) and if(n1%i==0 && n2%i==0) i.e (4%3==0 && 6%3==0) is FALSE then the below statements are not executed.

4th Iteration: for(i=4;i<=min;i++) i.e for(i=4;4<=4;i++) and if(n1%i==0 && n2%i==0) i.e (4%4==0 && 6%4==0) is FALSE then the below statements are not executed.

5th Iteration: as i is incremented so the value of i becomes 5 and the loop is exited because of 5>4. So finally the value of GCD becomes 2.

2. C Program to Find GCD of Two Numbers Using While loop

In this program, we will use while loop instead of for loop. Don’t be afraid of changing loop logic behind the program is same.

C

1

#include <stdio.h>

2

int main()

3

{

4

    int n1, n2;

5

    printf("Enter two positive integers to check GCD: ");

6

    scanf("%d %d",&n1,&n2);

7

    while(n1!=n2)

8

    {

9

        if(n1 > n2)

10

            n1 -= n2;

11

        else

12

            n2 -= n1;

13

    }

14

    printf("GCD = %d",n1);

15

    return 0;

16

}

Output:

3. GCD of two numbers Using Temporary Variable

In this program, we will use the Temporary Variable to calculate GCD of the entered number by the user.

C

1

#include <stdio.h>

2

int main()

3

{

4

    int Num1, Num2, GCD;

5

    printf("Please Enter two integer Values to find GCD \n");

6

    scanf("%d %d", &Num1, &Num2);

7

    if (Num1 == 0) {

8

        printf("GCD = %d", Num2);

9

    }

10

    while (Num2 != 0) {

11

        if (Num1 > Num2) {

12

            Num1 = Num1 - Num2;

13

    }

14

        else {

15

            Num2 = Num2 - Num1;

16

        }

17

    }

18

    GCD = Num1;

19

    printf("GCD = %d", GCD);

20

    return 0;

21

}

Output:

4. GCD of both Positive and Negative Number

In this program when the user enters the negative number then that negative number is first converted into positive then the GCD is printed on the screen.

C

1

#include <stdio.h>

2

int main()

3

{

4

    int n1, n2;

5

    printf("Enter two integers to find GCD: ");

6

    scanf("%d %d",&n1,&n2);

7

    // if user enters negative number, sign of the number is changed to positive

8

    n1 = ( n1 > 0) ? n1 : -n1;

9

    n2 = ( n2 > 0) ? n2 : -n2;

10

    while(n1!=n2)

11

    {

12

        if(n1 > n2)

13

            n1 -= n2;

14

        else

15

            n2 -= n1;

16

    }

17

    printf("GCD = %d",n1);

18

    return 0;

19

}

Output:

5. Gcd of Two Numbers using Recursion

Recursion is the method in which the function calls itself symmetrically or asymmetrically. Now we will see how GCD program is written Using Recursion.

C

1

#include <stdio.h>

2

long gcd(long x, long y);

3

int main()

4

{

5

    int Num1, Num2;

6

    printf("Please Enter two integer Values \n");

7

    scanf("%d %d", &Num1, &Num2);

8

    printf("GCD of %d and %d is = %d", Num1, Num2, gcd(Num1, Num2));

9

    return 0;

10

}

11

long gcd(long x, long y) 

12

{

13

  if (y == 0) {

14

    return x;

15

  }

16

  else {

17

    return gcd(y, x % y);

18

  }

19

}

Output:

6. GCD program using function

In this program, we will use a function called gcd() and find the gcd of two numbers using the function. Now let us see how the function works.

C

1

#include <stdio.h>

2

long gcd(long x, long y);

3

int main()

4

{

5

    int Num1, Num2;

6

    printf("Please Enter two integer Values \n");

7

    scanf("%d %d", &Num1, &Num2);

8

    printf("GCD of %d and %d is = %d", Num1, Num2,  gcd(Num1, Num2));

9

    return 0;

10

}

11

long gcd(long x, long y) 

12

{

13

    if (x == 0) {

14

        return y;

15

    }

16

    while (y != 0) {

17

        if (x > y) {

18

            x = x - y;

19

    }

20

        else {

21

            y = y - x;

22

        }

23

    }

24

    return x;

25

}

Output:

7. C Program to find GCD of n Numbers Simultaneously

Till now we find GCD using two numbers but in this program, we will ask the user to enter n numbers and their gcd will be printed on the screen after execution.

C

1

#include<stdio.h>

2

int main()

3

{

4

    printf("\nLearnprogramo-Programming made Simple\n\n\n");

5

    int x, y =- 1;

6

    printf("Enter numbers. and press 0 to exit program\n");

7

    while(1)    // infinite loop to take input

8

    {

9

        scanf("%d", &x);

10

        if(x < 1)

11

            break;

12

        else if(y ==- 1)    // only 1 number entered, its GCD is itself

13

            y = x;

14

        else if(x < y)

15

            y = gcd(x, y);

16

        else

17

            y = gcd(y, x);

18

    }

19

    printf("\n\n\nGCD of all the entered number is: %d", y);

20

    return 0;

21

}

22

// GCD of 2 numbers is calculated at a time

23

int gcd(int a, int b) 

24

{

25

    int i;

26

    /*

27

        a is the smallest of the two numbers 

28

        of which GCD is to be calculated

29

    */

30

    for(i = a; i >= 1; i--) 

31

    {

32

        // Greatest number that divides both the numbers

33

        if(a%i == 0 && b%i == 0) 

34

            break;  // exits the loop

35

    }

36

    return i;

37

}

Output:

in the above program, we entered 6 numbers simultaneously and press 0 to end the numbers. Finally, we get GCD of all numbers i.e 5.