Find GCD Of Two Numbers In C (Positive & Negative) With Examples

GCD stands for the Greatest Common Divisor, a mathematical concept used to calculate the greatest positive integer that divides two or more numbers without leaving a remainder. Mathematically speaking, the GCD of two numbers is obtained by first identifying all the shared factors between them and then finding the greatest number out of those.

This mathematical concept can be applied in programming and may find important use cases. In this article, we will discuss how to find the GCD of two numbers in C programming with the help of multiple methods and examples.

How To Find GCD Of Two Numbers In C?

In C language, there are primarily two approaches to finding the Greatest Common Divisor (GCD) of two numbers: the Euclidean algorithm and the prime factorization method. 

Method 1: Euclidean Algorithm

The Euclidean algorithm is an efficient and widely used method to find the GCD of two numbers in C programs. It is based on the principle that the GCD of two numbers remains the same if the larger number is replaced by the difference between the two numbers. Let's understand how the algorithm works.

• Step 1: Divide the larger number by the smaller number. Let A be the larger number, and B be the smaller number. Divide A by B and find the remainder R.
  A = B * Q + R
  Here, Q represents the quotient obtained when A is divided by B, and R is the remainder.

• Step 2: Repeat the process until the remainder becomes zero. Now, take B as the new larger number and R as the new smaller number. Divide B by R and find the new remainder R1.
  B = R * Q1 + R1
  Again, replace B with the previous value of R and R with R1, and continue this process until the remainder becomes zero. The last non-zero remainder you obtain will be the GCD of A and B.
  Mathematically, the process can be represented as:
  GCD(A, B) = GCD(B, R)
  GCD(B, R) = GCD(R, R1)
  …
  GCD(Rn, Rn+1) = GCD(Rn+1, 0) = Rn+1 (Final non-zero remainder)

• Step 3: The GCD is the last non-zero remainder obtained in the process. The GCD of A and B is the last non-zero remainder Rn+1.

Method 2: Prime Factorization

Another method to find the GCD of two numbers in C programming involves prime factorization.

• Step 1: Find the prime factors of both numbers A and B. Write both numbers as products of their prime factors. For example, if A = 12, it can be written as 2^2 * 3^1.
• Step 2: Identify the common prime factors and their minimum powers. The GCD will be the product of the common prime factors raised to the minimum powers between the two numbers.
  For example, if A = 12 (2^2 * 3^1) and B = 18 (2^1 * 3^2), the common prime factors are 2 and 3. The minimum powers are 2^1 and 3^1. Thus, GCD(A, B) = 2^1 * 3^1 = 6.

Both methods, the Euclidean algorithm and prime factorization, will yield the same GCD for the given two numbers. Also, The Greatest Common Divisor (GCD) of two or more integers is defined in mathematics as the greatest positive integer that divides all of the given integer values without leaving a remainder.

For example, the GCD of two numbers: 24 and 36.

• Step 1: We look for common divisors of both numbers, starting with 1 and moving upwards. We find that both 24 and 36 are divisible by 1.
• Step 2: Next, we check if they are divisible by 2. 24 is divisible by 2 (24 ÷ 2 = 12), and 36 is also divisible by 2 (36 ÷ 2 = 18).
• Step 3: Now, we check if they are divisible by 3. Both 24 and 36 are divisible by 3 (24 ÷ 3 = 8, and 36 ÷ 3 = 12)
• Step 4: Continuing in the same manner, we check if they are divisible by 4. Both 24 and 36 are divisible by 4 (24 ÷ 4 = 6, and 36 ÷ 4 = 9).
• Step 5: Moving on, we check if they are divisible by 5. Neither 24 nor 36 is divisible by 5.
• Step 6: We continue this process up to the square root of the smaller number (in this case, 24). Since 5 is greater than the square root of 24, we don't need to check further.
• Step 7: The largest positive integer that divides both 24 and 36 with no remainder (that is, the remainder is 0) is 12.

The Highest Common Factor (HCF), Highest Common Divisor (HCD), or Greatest Common Factor (GCF) is another name for the Greatest Common Divisor (GCD).

Simple Approach To Find GCD Of Two Numbers In C

A simple method to find the GCD of two numbers in C is to list all the divisors of both numbers and identify the greatest common factor they share. This process involves checking all potential divisors starting from 1 and going up to the smaller of the two numbers. The first number that divides both given numbers without leaving any remainder is the GCD.

While this approach is simple and easy to understand, it might become inefficient for large numbers because it involves testing all divisors. As an optimization, one can use more efficient algorithms like the Euclidean algorithm to find the GCD of two numbers in C, which avoids the exhaustive search for divisors and achieves faster results.

Here's the explanation of the mechanism of finding the GCD using the simple approach:

1. Start with two given numbers for which we want to find the GCD.
2. Begin the process by identifying the smaller of the two numbers; this will be our upper limit for potential divisors.
3. Set a divisor variable initially to 1 (the smallest possible divisor).
4. Check if the divisor divides both given numbers without leaving a remainder (i.e., the remainder is 0).
5. If the divisor divides both numbers, it is a common factor.
6. Keep track of the largest common factor found so far.
7. Increment the divisor and repeat the check in step 4 until reaching the smaller number (upper limit).
8. The last divisor that divides both numbers without a remainder is the Greatest Common Divisor (GCD).

Given below is the pseudocode to show how we can use this simple approach to find the GCD of two numbers in C language.

Pseudocode:

FUNCTION findGCD(num_1, num_2)
min_num = MIN(num_1, num_2)
FOR i = min_num TO 1 STEP -1
IF num_1 MOD i == 0 AND num_2 MOD i == 0 THEN
RETURN i
END IF
END FOR
RETURN 1 // Every number is divisible by 1
END FUNCTION

FUNCTION main()
num_1 = 48
num_2 = 18

gcd = findGCD(num_1, num_2)
PRINT "The GCD of " + num_1 + " and " + num_2 + " is " + gcd
RETURN 0
END FUNCTION

Let's look at a sample C program that showcases how this approach can be implemented in the C coding language.

Code Example:

I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgZmluZEdDRChpbnQgbnVtXzEsIGludCBudW1fMikgewppbnQgbWluX251bSA9IChudW1fMSA8IG51bV8yKSA/IG51bV8xIDogbnVtXzI7CmZvciAoaW50IGkgPSBtaW5fbnVtOyBpID49IDE7IGktLSkgewppZiAobnVtXzEgJSBpID09IDAgJiYgbnVtXzIgJSBpID09IDApIHsKcmV0dXJuIGk7fQp9CnJldHVybiAxOyAvLyBFdmVyeSBudW1iZXIgaXMgZGl2aXNpYmxlIGJ5IDEKfQoKaW50IG1haW4oKSB7CmludCBudW1fMSA9IDQ4OwppbnQgbnVtXzIgPSAxODsKCmludCBnY2QgPSBmaW5kR0NEKG51bV8xLCBudW1fMik7CnByaW50ZigiVGhlIEdDRCBvZiAlZCBhbmQgJWQgaXMgJWRcbiIsIG51bV8xLCBudW1fMiwgZ2NkKTsKCnJldHVybiAwOwp9

Output:

The GCD of 48 and 18 is 6

Explanation:

In the simple C program, we begin by including the essential header file <stdio.h> for input-output operations.

1. We then define a function called findGCD to calculate the GCD of two integers. In this function-
   •  First, we determine the smaller of the two input numbers using the ternary operator. The outcome is stored in the min_num variable.
   • Then, we use a for loop, which begins with the control variable i=min_num and runs until i remains less than equal to 1. After every iteration, we decrement the value of i by 1.
   • Inside the loop, we use an if-statement to check if both input numbers are divisible by the current loop variable without remainder. We use the relational equality operator, the arithmetic modulo operator and the logical AND operator inside the condition.
   • If the condition is met, we return the current loop variable, which represents the GCD.
   • If no common divisor greater than 1 is found, we return 1, indicating that both numbers are divisible by 1.
2. We then initiate the main() function, which is the entry point of the program's execution.
3. Inside the main, we initialize two integer variables, num_1 and num_2, with values 48 and 18, respectively.
4. After that, we call the findGCD() function with these two numbers as arguments and store the result in the variable gcd.
5. Finally, we print the values of num_1, num_2, and gcd using the printf() function.
6. The program returns 0 to indicate successful execution to the operating system.

Time Complexity: O(min(num_1, num_2)) - where min is the minimum of the two input numbers.
Space Complexity: O(1) - constant, independent of the input size.

The Euclidean Algorithm To Find GCD Of Two Numbers In C

The Euclidean Algorithm is a mathematical procedure for calculating the Greatest Common Divisor (GCD) of two integers. It was introduced by the ancient Greek mathematician Euclid and is one of the oldest and most efficient algorithms known.

• The Euclidean Algorithm's primary goal is to compute the GCD of two positive integers, say a and b.
• It repeatedly applies the notion that if the smaller number is subtracted from the larger number, the GCD of the two numbers remains constant until one of the numbers becomes zero.
• At this point, the GCD will be the greatest common divisor of the original two numbers.

Approach: The Euclidean Algorithm operates on the principle: If a = b Q + R, and Q is the quotient, and R is the remainder, then GCD(a, b) = GCD(b, R). Here's how the Euclidean Algorithm to find the GDC of two numbers in C works:

1. Consider the two positive integers a and b.
2. Subtract a from b to get the quotient Q and the remainder R.
3. If R equals 0, then b is the GCD of a and b, and the algorithm exits.
4. Otherwise, assign the value of variable a to variable b and the value of b to R.
5. Repeat steps 2–4 until R equals zero.
6. The last non-zero remainder obtained in the process will be the GCD of the original two values.

Code Example:

I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBGdW5jdGlvbiB0byBjYWxjdWxhdGUgdGhlIEdDRCBvZiB0d28gbnVtYmVycyB1c2luZyB0aGUgRXVjbGlkZWFuIEFsZ29yaXRobQppbnQgZ2NkKGludCBhLCBpbnQgYikgewp3aGlsZSAoYiAhPSAwKSB7CmludCB0ZW1wID0gYjsKYiA9IGEgJSBiOwphID0gdGVtcDt9CnJldHVybiBhOwp9CgppbnQgbWFpbigpIHsKaW50IG51bTEsIG51bTI7CnByaW50ZigiRW50ZXIgdHdvIG51bWJlcnM6ICIpOwpzY2FuZigiJWQgJWQiLCAmbnVtMSwgJm51bTIpOwoKaW50IHJlc3VsdCA9IGdjZChudW0xLCBudW0yKTsKcHJpbnRmKCJUaGUgR0NEIG9mICVkIGFuZCAlZCBpczogJWRcbiIsIG51bTEsIG51bTIsIHJlc3VsdCk7CgpyZXR1cm4gMDsKfQ==

Output:

Enter two numbers: 18 24
The GCD of 18 and 24 is: 6

Explanation:

In the example C code- 

1. We define the gcd() function to calculate the GCD of two integers using the Euclidean Algorithm. Naturally, it takes two integers as parameters. Inside the function-
   • We have a while loop that continues iterations until b becomes 0. This is a key step in the Euclidean Algorithm.
   • In the loop, we store the value of b in temporary variable temp.
   • Then, we update b to become the remainder of a divided by b and update assign variable a with the previous value of b. This process continues until b becomes 0.
   • Once b becomes 0, the loop exits, and we return the value of a, which represents the GCD of the two input numbers.
2. In the main() function, we declare two integer variables, num1 and num2, to store user input.
3. We prompt the user to enter two numbers using printf(), read the input using scanf(), and store them in respective variables using the address-of/ reference operator. 
4. After that, we call the gcd() function with the input numbers num1 and num2 as arguments and store the result in the variable result.
5. Then, we print the input numbers num1 and num2 along with the calculated GCD result using the printf() function.
6. Finally, the program terminates with a returns 0 statement, indicating successful execution without any errors.

GCD Of Two Numbers In C Using For Loop & If-Statement

To find the Greatest Common Divisor (GCD) of two numbers using a for loop and if statement, we can use the concept of the Euclidean Algorithm. As discussed above, the Euclidean Algorithm repeatedly applies the principle that the GCD of two numbers remains the same if the smaller number is subtracted from the larger number until one of the numbers becomes zero. The GCD obtained at this point will be the greatest common divisor of the original two numbers.

Here's how to implement the GCD of two numbers in C programs using a for loop and if statement:

1. Take two positive integers, a and b, where a should be greater than or equal to b. If necessary, you can swap the values to ensure this condition.
2. Start a for loop from control variable i equal to the minimum of a and b and run it until it reaches 1. The loop will check for common factors starting from the smallest possible factor.
3. Inside the for loop, use an if statement to check if both a and b are divisible by the current value of i (i.e., if "a % i == 0" and "b % i == 0" are both true).
4. If the condition in the if statement is met, it means i is a common factor of both a and b. At this point, i is the GCD, so break out of the loop.
5. After the loop, the variable i will hold the GCD of the original two numbers.

Code Example:

I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBGdW5jdGlvbiB0byBjYWxjdWxhdGUgdGhlIEdDRCBvZiB0d28gbnVtYmVycyB1c2luZyBmb3IgbG9vcCBhbmQgaWYgc3RhdGVtZW50CmludCBnY2QoaW50IGEsIGludCBiKSB7CmludCBtaW4gPSAoYSA8IGIpID8gYSA6IGI7IC8vIEZpbmQgdGhlIG1pbmltdW0gb2YgdGhlIHR3byBudW1iZXJzCmZvciAoaW50IGkgPSBtaW47IGkgPj0gMTsgaS0tKSB7CmlmIChhICUgaSA9PSAwICYmIGIgJSBpID09IDApIHsKcmV0dXJuIGk7IC8vIGkgaXMgdGhlIEdDRCwgc28gcmV0dXJuIGl0Cn0KfQpyZXR1cm4gMTsgLy8gRGVmYXVsdCBHQ0QgaXMgMSBpZiBubyBjb21tb24gZmFjdG9yIGlzIGZvdW5kCn0KCmludCBtYWluKCkgewppbnQgbnVtMSwgbnVtMjsKcHJpbnRmKCJFbnRlciB0d28gbnVtYmVyczogIik7CnNjYW5mKCIlZCAlZCIsICZudW0xLCAmbnVtMik7CgppbnQgcmVzdWx0ID0gZ2NkKG51bTEsIG51bTIpOwpwcmludGYoIlRoZSBHQ0Qgb2YgJWQgYW5kICVkIGlzOiAlZFxuIiwgbnVtMSwgbnVtMiwgcmVzdWx0KTsKCnJldHVybiAwOwp9

Output:

Enter two numbers: 18 24
The GCD of 18 and 24 is: 6

Explanation:

In the sample C code-

1. We define the gcd() function to calculate the GCD of two integers using a for loop and if statement.
   • Inside the function, we first find the minimum of the two input numbers, a and b, using a ternary operator. The outcome is stored in the min variable.
   • Next, we initiate a for loop starting from the minimum value down to 1. This loop iterates through potential divisors of the two numbers to find their greatest common divisor.
   • Within the loop, we use an if statement to check if both a and b are divisible by the current loop variable i without any remainder.
   • If they are, we return the current loop variable i, which represents the GCD of the two input numbers.
   • If no common divisor greater than 1 is found, we return 1, indicating that both numbers are divisible by 1.
2. In the main() function, we declare two integer variables, num1 and num2, to store user input.
3. We prompt the user to enter two numbers and store the values in respective variables.
4. Next, we call the gcd() function with the input numbers num1 and num2 as arguments and store the result in the variable result.
5. Finally, we print the input numbers num1 and num2 along with the calculated GCD result using printf.

GCD Of Two Numbers In C Using While Loop

To find the Greatest Common Divisor (GCD) of two numbers using a while loop, we can still apply the concept of the Euclidean Algorithm. The Euclidean Algorithm repeatedly applies the principle that the GCD of two numbers remains the same if the smaller number is subtracted from the larger number until one of the numbers becomes zero. The GCD obtained at this point will be the greatest common divisor of the original two numbers.

Approach: Here's how to implement the GCD of two numbers using a while loop in a step-by-step explanation:

1. Take two positive integers, x and y, where the value x must be greater than or equal to the value of y. If necessary, you can swap the values to ensure this condition.
2. Start a while loop that continues iterating as long as the value of y as long as the condition y not equals zero remains true, i.e., y != 0.
3. Inside the while loop, calculate the remainder of the division of x by y (i.e., x % y) and store it in a temporary variable.
4. Update the value of x to the value of y and then the value of y to the remainder obtained in step 3.
5. Repeat steps 2-4; that is, the while loop continues until the condition becomes false. At this point, the value of x will be the GCD of the original two numbers.

To know the code implementation of this approach to find the GCD of two numbers in C, check out the example given in the Euclidean section.

The GCD Of Two Numbers In C With User-Defined Function

A user-defined function refers to when you create your own function using a combination of techniques that best meet your needs. It is a flexible way to deal with many programming issues. Naturally, we can also create a user-defined/ customer function to calculate the GCD of two numbers in C program. In this section, we will revisit the Euclidean Algorithm to create a custom function and find the GCD. 

Code Example:

I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBVc2VyLWRlZmluZWQgZnVuY3Rpb24gdG8gY2FsY3VsYXRlIHRoZSBHQ0Qgb2YgdHdvIG51bWJlcnMgdXNpbmcgdGhlIEV1Y2xpZGVhbiBBbGdvcml0aG0KaW50IGdjZChpbnQgYSwgaW50IGIpIHsKd2hpbGUgKGIgIT0gMCkgewppbnQgdGVtcCA9IGEgJSBiOwphID0gYjsKYiA9IHRlbXA7fQpyZXR1cm4gYTsgLy8gYSBpcyB0aGUgR0NECn0KCmludCBtYWluKCkgewppbnQgbnVtMSA9IDIyLCBudW0yID0gNDI7CgppbnQgcmVzdWx0ID0gZ2NkKG51bTEsIG51bTIpOwpwcmludGYoIlRoZSBHQ0Qgb2YgJWQgYW5kICVkIGlzOiAlZFxuIiwgbnVtMSwgbnVtMiwgcmVzdWx0KTsKCnJldHVybiAwOwp9

Output:

The GCD of 22 and 42 is: 2

Explanation:

In the C code example- 

1. We define the gcd() function to calculate the GCD of two numbers, a and b, that it takes as input.
   • Inside the function, we have a while loop, which determines if the value of b is not equal to zero. If the condition is false, the loop is terminated.
   • If the condition is true, the loop assigns the remainder of the division of a by b to the variable temp.
   • It then assigns the value of b to variable a and the value of temp to variable b.
   • This iteration continues until the condition becomes false, after which the loop terminates, and the function returns the value of variable a. This is the GCD of the two numbers.
2. In the main() function, we declare and initialize two integer data type variables, num1 and num2, with values of 22 and 42, respectively.
3. We then call the gcd() function and pass num1 and num2 as arguments. The outcome of the function is stored in the result variable. 
4. We print the outcome to the console using the printf() function and a formatted string message. Inside the string, the %d format specifier represents an integer value and the newline escape sequence (\n) shifts the cursor to the next line.
5. The program finally terminates with a return 0 statement.

Find GCD Of Two Numbers In C Using Modulo Operator

The modulo arithmetic operator represented by the per cent symbol (%) calculates the remainder of the division operation between two variables. We can use this operator to continuously divide two numbers until the remainder becomes zero. The divisor, which leaves no remainder then, will be the GCD of the two numbers. Below is an example C code showing how this can be implemented in practice.

Code Example:

I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBGdW5jdGlvbiB0byBjYWxjdWxhdGUgdGhlIEdDRCBvZiB0d28gbnVtYmVycwppbnQgZ2NkKGludCBhLCBpbnQgYikgewp3aGlsZSAoYiAhPSAwKSB7CmludCB0ZW1wID0gYSAlIGI7CmEgPSBiOwpiID0gdGVtcDt9CnJldHVybiBhOyAvLyBhIGlzIHRoZSBHQ0QKfQoKaW50IG1haW4oKSB7CmludCBudW0xID0gMzMsIG51bTIgPSAxMTsKCmludCByZXN1bHQgPSBnY2QobnVtMSwgbnVtMik7CnByaW50ZigiVGhlIEdDRCBvZiAlZCBhbmQgJWQgaXM6ICVkXG4iLCBudW0xLCBudW0yLCByZXN1bHQpOwoKcmV0dXJuIDA7Cn0=

Output:

The GCD of 33 and 11 is: 11

Explanation:

In the sample code- 

1. We begin by defining a function called gcd(), which takes two integers as parameters and calculates their GCD. Here-
   
   • First, we use a while loop to check if the value of b (which is the divisor) is not equal to zero. The loop continues iterations until this condition becomes false.
   • In the loop, we calculate the remainder of a by b using the modulo operator (a % b) and store it in a temporary variable temp.
   • We update a with the value of b and b with the value of temp. This step ensures that a becomes b and b becomes the remainder.
   • This process continues until b becomes 0, at which point a holds the value of the GCD.
   • We return the value of a, which represents the GCD of the two input numbers.
2. In the main() function, we declare and initialize integer variables num1 and num2 with values 33 and 11, respectively. The variables are declared in a single line, separated by a comma. 
3. After that, we call the gdc() function with num1 and num2 as arguments and store the result in the variable result.
4. Then, we display the value of the result variable to the console, and the program terminates successfully.

GCD Of Two Numbers In C Using Recursion

In the recursive approach, the function to calculate the GCD will call itself with a modified version of the input until the base case is reached. The base case is the scenario where one of the numbers becomes zero, at which point the function can return the other number as the GCD.

The premise of defining the recursive function is the Euclidean Algorithm, which repeatedly applies the principle that the GCD of two numbers remains the same if the smaller number is subtracted from, the larger number until one of the numbers becomes zero. 

Code Example:

I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBSZWN1cnNpdmUgZnVuY3Rpb24gdG8gY2FsY3VsYXRlIHRoZSBHQ0Qgb2YgdHdvIG51bWJlcnMKaW50IGdjZChpbnQgYSwgaW50IGIpIHsKaWYgKGIgPT0gMCkgewpyZXR1cm4gYTsgLy8gQmFzZSBjYXNlOiBHQ0QgaXMgZm91bmQsIHJldHVybiAnYScKfSBlbHNlIHsKcmV0dXJuIGdjZChiLCBhICUgYik7IC8vIFJlY3Vyc2l2ZSBjYWxsIHdpdGggbW9kaWZpZWQgaW5wdXRzCn0KfQoKaW50IG1haW4oKSB7CmludCBudW0xLCBudW0yOwpwcmludGYoIkVudGVyIHR3byBudW1iZXJzOiAiKTsKc2NhbmYoIiVkICVkIiwgJm51bTEsICZudW0yKTsKCmludCByZXN1bHQgPSBnY2QobnVtMSwgbnVtMik7CnByaW50ZigiVGhlIEdDRCBvZiAlZCBhbmQgJWQgaXM6ICVkXG4iLCBudW0xLCBudW0yLCByZXN1bHQpOwoKcmV0dXJuIDA7Cn0=

Output:

Enter two numbers: 18 24
The GCD of 18 and 24 is: 6

Explanation:

In the C program example- 

1. As mentioned in code comments, we define a gcd() function as a recursive function to calculate the greatest common divisor (GCD) of two integers.
   • Inside the function, there's a base case check, i.e., if b is equal to 0, it means we have found the GCD, so we return a.
   • If the base case is not met, we make a recursive call to gcd with the arguments b and a % b. This is a key step in the Euclidean Algorithm.
   • The recursive call continues until the base case is reached (i.e., until b becomes 0), at which point the GCD is found, and the recursion unwinds.
2. In the main() function, we declare two integer variables, num1 and num2, to store user input.
3. We prompt the user to enter two numbers using printf, read the input values and store them in respective variables using scanf().
4. After that, we call the() gcd function with the input numbers num1 and num2 as arguments and store the result in the variable result.
5. Finally, we print the input numbers num1 and num2 along with the calculated GCD result using printf.

GCD Of Two Numbers In C Using Inbuilt Function

In C, there is no direct inbuilt function in the standard library to calculate the Greatest Common Divisor (GCD) of two numbers like in C++. However, you can still use a standard function from the <stdlib.h> library called abs() to calculate the absolute value of a number. This helps expand the scope of implementation to negative numbers. We can then create a function that follows the Euclidean methodology to find the GCD of two numbers in C.

Approach: Here's how you can calculate the GCD of two numbers in C using the abs() function:

1. Include the necessary header file #include <stdlib.h>.
2. Define a user-defined function named gcd that takes two integer arguments a and b and returns an integer value (the GCD).
3. Inside the gcd function, use the abs() function to calculate the absolute values of a and b to ensure that negative numbers don't affect the GCD calculation.
4. Implement the Euclidean Algorithm using the absolute values of a and b to find the GCD.
5. Return the GCD as the final result.

Code Example:

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCi8vIEZ1bmN0aW9uIHRvIGNhbGN1bGF0ZSB0aGUgR0NEIG9mIHR3byBudW1iZXJzCmludCBnY2QoaW50IGEsIGludCBiKSB7CmEgPSBhYnMoYSk7CmIgPSBhYnMoYik7CndoaWxlIChiICE9IDApIHsKaW50IHRlbXAgPSBhICUgYjsKYSA9IGI7CmIgPSB0ZW1wO30KcmV0dXJuIGE7IC8vIGEgaXMgdGhlIEdDRAp9CgppbnQgbWFpbigpIHsKaW50IG51bTEsIG51bTI7CgpwcmludGYoIkVudGVyIHR3byBudW1iZXJzOiAiKTsKc2NhbmYoIiVkICVkIiwgJm51bTEsICZudW0yKTsKCmludCByZXN1bHQgPSBnY2QobnVtMSwgbnVtMik7CnByaW50ZigiVGhlIEdDRCBvZiAlZCBhbmQgJWQgaXM6ICVkXG4iLCBudW0xLCBudW0yLCByZXN1bHQpOwoKcmV0dXJuIDA7Cn0=

Output:

Enter two numbers: -18 -24
The GCD of -18 and -24 is: 6

Explanation:

In the above code,

1. We define the gcd() function to take two integer parameters and calculate their GCD. In the function-
   • We first take the absolute values of a and b using the abs() function to handle negative inputs.
   • Then, we use a while loop to check if the divisor, i.e., b, is not equal to zero. If so, then the loop continues until b becomes 0. 
   • The loop first calculates the remainder of a by b and stores it in a temporary variable temp.
   • We update a with the value of b and b with the value of temp. This step ensures that a becomes b and b becomes the remainder.
   • This process continues until b becomes 0, at which point a holds the value of the GCD.
   • The function returns the value of a, which represents the GCD of the two input numbers.
2. In the main() function, we declare two integer variables, num1 and num2, to store user input.
3. We then prompt the user to provide two integer values and store them in respective variables.
4. After that, we call the gcd() function with the input numbers num1 and num2 as arguments and store the result in the variable result.
5. Finally, we print the input numbers num1 and num2 along with the calculated GCD result using the printf() function.

GCD Of Positive & Negative Number With User Input

To calculate the Greatest Common Divisor (GCD) of two numbers, including both positive and negative numbers, with user input, we can follow the same approach using the Euclidean Algorithm as previously described. This algorithm works for both positive and negative numbers, and we'll use the abs() function.

It is a mathematical function commonly found in programming languages and libraries. It stands for absolute value and is used to determine the distance of a number from zero on the number line, disregarding its sign. In other words, the absolute value of a number is always a positive value or zero to ensure that negative numbers do not affect the GCD calculation.

Code Example:

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCi8vIEZ1bmN0aW9uIHRvIGNhbGN1bGF0ZSB0aGUgR0NEIG9mIHR3byBudW1iZXJzLCBib3RoIG5lZ2F0aXZlIGFuZCBwb3NpdGl2ZQppbnQgZ2NkKGludCBhLCBpbnQgYikgewphID0gYWJzKGEpOwpiID0gYWJzKGIpOwp3aGlsZSAoYiAhPSAwKSB7CmludCB0ZW1wID0gYSAlIGI7CmEgPSBiOwpiID0gdGVtcDt9CnJldHVybiBhOyAvLyBhIGlzIHRoZSBHQ0QKfQoKaW50IG1haW4oKSB7CmludCBudW0xLCBudW0yOwpwcmludGYoIkVudGVyIHR3byBudW1iZXJzOiAiKTsKc2NhbmYoIiVkICVkIiwgJm51bTEsICZudW0yKTsKCmludCByZXN1bHQgPSBnY2QobnVtMSwgbnVtMik7CnByaW50ZigiVGhlIEdDRCBvZiAlZCBhbmQgJWQgaXM6ICVkXG4iLCBudW0xLCBudW0yLCByZXN1bHQpOwoKcmV0dXJuIDA7Cn0=

Output:

Enter two numbers: -18 24
The GCD of -18 and 24 is: 6

Code Explanation:

In the sample C code- 

• We first define the gcd() function, which takes two integer values and calculates their GCD. Inside-
  • We use the abs() function to get the absolute value of both numbers so that the operation is not disturbed by negative values.
  • We then use a while loop to calculate the remainder of a by b and store the outcome in the temp variable.
  • By reassigning the value of the b variable to a and then temp to b, we ensure that the loop iteratively checks every divisor and finds the one that leaves no remainder.
  • This process continues until b becomes 0, at which point a holds the value of the GCD, and the function returns this value.
• In the main() function, we declare two integer variables, num1 and num2, to prompt the user to input their values. 
• Then, we call the gcd() function with the input numbers num1 and num2 as arguments and store the result in the variable result.
• The program displays these values using the printf() function before terminating successfully. 

Time & Space Complexity Comparison

Time Complexity: Time complexity is a measure of the amount of time an algorithm takes to run as a function of the input size. It provides an estimation of the number of basic operations an algorithm performs as the input size increases. In other words, it quantifies the efficiency of an algorithm in terms of time consumption.

Space Complexity:  Space complexity refers to the amount of memory an algorithm uses as a function of the input size. It provides an estimation of the additional memory required by an algorithm to execute and store intermediate variables. Space complexity is also expressed using Big O notation.

Here is a table showcasing the complexity comparison of the methods of calculating the GCD of two number in C, as discussed above:

Conclusion

In this article, we have explored different methodologies for calculating the GCD of two numbers in C. These methods include looping statements (for and while), operators in C, user-defined functions, the Euclidean approach, recursion, etc.

Euclid's algorithm emerged as a prominent technique due to its optimized time complexity of O(log min(a, b)), which makes it ideal for handling larger numbers efficiently. Incorporating these methodologies into one's toolkit can prove invaluable when working with integer values, whether in mathematical problem-solving, algorithm design, or computer programming. By understanding these techniques, individuals gain the ability to choose the most appropriate approach based on the specific context, optimizing the computation of GCDs for a diverse range of scenarios.

Frequently Asked Questions

Q. How do you find the GCD of numbers?

There exist various strategies for determining the Greatest Common Divisor (GCD) of numbers:

1. Iterative Exploration: Traverse the range from 1 to the smaller of the two numbers. Identify the largest value within this range that evenly divides both numbers without any remainder.
2. Subtraction Approach: Engage in a repetitive process of subtracting the smaller number from the larger one until they equate. The common value achieved through this process is the GCD.
3. Euclidean Algorithm: Adopt the efficient Euclidean algorithm, which centres on finding the remainder when the larger number is divided by the smaller number. This procedure is repeated with the smaller number and the remainder until the remainder becomes zero. The last non-zero remainder signifies the GCD.
4. Prime Factor Analysis: Decode the prime factorization of both numbers. Identify the shared prime factors and multiply them to acquire the GCD.

Q. What is the GCD of 14 and 2?

The Euclidean Algorithm involves repeatedly taking the remainder of the larger number divided by the smaller number and continuing this process until the remainder becomes zero. The last non-zero remainder obtained in this process is the GCD of the two numbers in C.

Let's calculate:

1. Divide 14 by 2: Quotient = 7, Remainder = 0
2. Since the remainder is 0, the algorithm terminates.

The last non-zero remainder is 0, which means that the GCD of 14 and 2 is the divisor from the previous step, which is 2. So, the GCD of 14 and 2 is indeed 2.

Q. What are the GCD and LCM of integers?

GCD (Greatest Common Divisor): The GCD of two or more integers is the largest positive integer that divides each of the given integers without leaving a remainder. It's also known as the greatest common factor.

LCM (Least Common Multiple): The LCM of two or more integers is the smallest positive integer that is divisible by each of the given integers.

Relationship between GCD and LCM: GCD(a, b) * LCM(a, b) = |a * b|

Q. What are the steps to calculate the GCD of two numbers in C?

To calculate the Greatest Common Divisor (GCD) of two numbers, you can use various methods like the Euclidean Algorithm, prime factorization, or iterative methods. Here are the steps to calculate the GCD of two numbers in C using the Euclidean Algorithm:

Euclidean Algorithm:

1. Choose Two Numbers: Start with the two numbers for which you want to find the GCD.
2. Divide and Find Remainder: Divide the larger number by the smaller number and find the remainder. Let's call this remainder R.
3. Swap and Repeat: Replace the larger number with the smaller number and the smaller number with the remainder R obtained in the previous step.
4. Repeat Until Remainder is 0: Continue dividing the new larger number by the new smaller number to get a new reminder. Keep repeating this process until the remainder becomes 0.
5. Last Non-Zero Remainder: The GCD is the last non-zero remainder obtained in the previous step.

Q. Is GCD positive integers?

Yes, the Greatest Common Divisor (GCD) is typically calculated for positive integers. It's defined as the largest positive integer that divides two or more positive integers without leaving a remainder. In other words, the GCD represents the greatest common factor that these positive integers share.

Q. What is the GCD of 2a and 2b?

The GCD of 2a and 2b, where "a" and "b" are positive integers, is 2. This is because both 2a and 2b have a common factor of 2, and the greatest common divisor represents the largest positive integer that divides both numbers without leaving a remainder. In this case, 2 is the largest factor that divides both 2a and 2b without leaving a remainder, making it the GCD.

Q. What is the GCD of an integer and 0?

The greatest common divisor (GCD) of any non-zero integer and 0 is the absolute value of that integer. In mathematical terms:

GCD(a, 0) = |a|, where "a" is a non-zero integer.

This is because any non-zero integer is a divisor of itself, and since 0 is not a divisor of any non-zero integer, the largest common divisor in this case is the absolute value of the non-zero integer.

Q. What is the GCD of negative integers?

The concept of the greatest common divisor (GCD) extends to negative integers as well. When computing the GCD of negative numbers, the focus shifts to their absolute values, as the GCD seeks shared factors. For instance, contemplate the GCD of -6 and -9. This is akin to the GCD of their absolute counterparts, 6 and 9. Consequently, the GCD remains 3.

In essence, calculating the GCD of negative integers involves utilizing the absolute values and applying the identical principles applicable when calculating the GCD of two numbers in C (positive).

Here are a few more articles you might be interested in reading:

1. Control Statements In C | The Beginner's Guide (With Examples)
2. 5 Types Of Literals In C & More Explained With Examples!
3. Compilation In C | Detail Explanation Using Diagrams & Examples
4. Understanding Constant In C: How To Define, Syntax, and Types
5. Pointers In C | Ultimate Guide With Easy Explanations (+Examples)