GCD of Two Numbers in C

Prerequisites

• C Programming Operators
• C for Loop
• C if...else Statement
• C while Loop
• Do...while Loop

Different Ways to Get GCD of Two Numbers in C

1. GCD Using for loop and if Statement

We can use for loop to find the GCD of two numbers using the algorithm mentioned in the previous section. Let's see a program to find GCD of two numbers in C using for loop.

Output

Explanation

In this example, we are iterating on all numbers from 1 to the minimum of two numbers. If any number in this range divides both the numbers a and b, we are updating our answer. This way, we find the last/greatest number in the range 1 to min(a, b) that divides both the numbers.

We are iterating until the minimum of two numbers because any number greater than the minimum will always leave a remainder when divided by the minimum number. For this reason, a number greater than the minimum of two numbers can never be the GCD of those two numbers.

2. GCD Using while loop and if...else Statement

We can also find the GCD of two numbers using a while loop by because

• If a smaller number is subtracted from the larger number (that is, reduce larger number by smaller number), GCD does not change. Therefore, if we keep repeatedly subtracting the larger of two numbers, we end up with the GCD of two numbers.

Let's consider a program that uses this fact to find GCD of two numbers in C using a while loop.

Output

Explanation

In this example, we are using the fact that GCD remains the same when the larger of two numbers is subtracted by, the smaller of the two numbers. We are using a while loop in the above code to reduce the larger number among a and b until the numbers are equal. When both a and b become equal, our GCD will be the value of either number (since both are now equal).

3. GCD for both positive and negative numbers

The Euclidean algorithm is a way to find the GCD of two numbers. It works as follows:

1. Given two positive integers a and b, if a > b, divide a by b and replace a with the remainder (a % b).
2. Repeat the above step until b becomes 0. When b becomes 0, the GCD is the remaining value of a.

For negative numbers, the GCD is still calculated in the same way, but you should work with their absolute values and then negate the result if necessary.

Sample Output:

Here are some sample inputs and their corresponding outputs using the code above:

1. For input 12 and 18:

   Enter two integers: 12 18
   GCD of 12 and 18 is: 6
   

2. For input -12 and 18:

   Enter two integers: -12 18
   GCD of -12 and 18 is: 6
   

3. For input -12 and -18:

   Enter two integers: -12 -18
   GCD of -12 and -18 is: 6
   

The code first takes two integers as input, calculates the GCD using the gcd function, and then prints the result. It correctly handles both positive and negative numbers.

4. Get the GCD of N numbers from the user

The Greatest Common Divisor of more than two numbers is equals the product of the prime factors common to all the numbers, or we can calculate it by repeatedly taking the GCDs of pairs of two numbers.

For an array of positive integers, we do the following. We will check for the result until the result at any step becomes 1. When either of the two numbers becomes one, we will return 1 from the function as gcd(1,x)=1.

Let's consider the program to find GCD of N numbers.

Output

Explanation

Here, we first take gcd_ as the first element in the array, and then we iterate on all remaining elements in the array and find the gcd of the current element in the array with gcd_. This way, we calculate GCDs of N numbers by repeatedly taking the GCDs of pairs of two numbers.

5. Get the GCD of two numbers using user defined function

• You can calculate the GCD of two numbers using the Euclidean algorithm, which is an efficient way to find the GCD.
• The algorithm works by repeatedly taking the remainder of the larger number divided by the smaller number until the smaller number becomes zero. The last non-zero remainder is the GCD of the two numbers.

Here's the C code to find the GCD of two numbers using a user-defined function:

• When you run the above code, it will prompt you to enter two numbers. After entering the numbers, it will calculate and display the GCD of those two numbers.

Here's an example of how the program works:

In this example, the GCD of 24 and 18 is 6, and the program correctly calculates and displays it.

6. GCD of two numbers using the modulo operator

The greatest common divisor (GCD) of two numbers is the largest positive integer that divides both of them without leaving a remainder. One common way to calculate the GCD of two numbers is to use the Euclidean algorithm. The Euclidean algorithm is an efficient method for finding the GCD of two integers.

The algorithm works as follows:

1. Given two integers a and b, where a is greater than or equal to b.
2. Compute the remainder of the division of a by b and store it in r.
3. Replace a with b and b with r.
4. Repeat steps 2 and 3 until b becomes 0.
5. The value of a when b becomes 0 is the GCD of the original two numbers.

Here's a C program that calculates the GCD of two numbers using the modulo operator:

When you run the code and enter two numbers, it will calculate and display the GCD of those two numbers. For example:

In this example, the GCD of 24 and 18 is 6, which is correctly calculated using the Euclidean algorithm with the modulo operator.

7. GCD of two numbers using Recursion

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. One common way to find the GCD of two numbers is to use the Euclidean algorithm, which can be implemented using recursion. The algorithm is based on the fact that the GCD of two numbers remains the same if we subtract the smaller number from the larger number until both numbers become equal.

Here's how the algorithm works:

1. If one of the numbers is 0, the GCD is the other number.
2. Otherwise, recursively find the GCD of the smaller number and the remainder when the larger number is divided by the smaller number.

Here's a C program to find the GCD of two numbers using recursion:

When you run the program and input two numbers, it will calculate and display the GCD of those numbers. Here's an example:

In this example, the GCD of 56 and 48 is calculated as 8 using the recursive GCD function.

8. GCD of three numbers using if_else and for loop

The Greatest Common Divisor (GCD) of three numbers is the largest number that can exactly divide all three numbers without leaving a remainder. You can calculate the GCD of three numbers using a for loop and the if-else statement. One common method to find the GCD of three numbers is to first find the GCD of the first two numbers and then find the GCD of the result with the third number.

Here's a simple algorithm to find the GCD of three numbers:

1. Find the GCD of the first two numbers (let's call it gcd1).
2. Find the GCD of gcd1 and the third number (let's call it gcd2).
3. gcd2 is the GCD of all three numbers.

Here's a C program that calculates the GCD of three numbers using for loops and if-else statements:

When you run the program and input three numbers, it will calculate and display the GCD of those three numbers.

For example:

In this example, the GCD of 24, 36, and 48 is 12.