The greatest common divisor (GCD) is the largest positive integer that is also a common divisor of a given set of positive integers. It is also known as the highest common factor (HCF) or the greatest common factor (GCF). The greatest common divisor of a pair of positive integers (a, b) is defined as the greatest positive number that is both positive integers' common factor (a, b). The GCD of any two numbers is never negative or zero since the smallest positive integer shared by any two numbers is always 1. let's take two numbers 75 and 30 so the highest number that can divide both numbers will be 15. For example: The numbers that can divide both 75 and 30 are [1,3,5,15] so the highest number among these is 15 so it will be the GCD of 75 and 30. Explanation: let's take two numbers 128 and 32 so the highest number that can divide both numbers will be 32. Example 2: The numbers that can divide both 128 and 32 are [1,2,4,8,16,32] so the highest number among these is 32 so it will be the GCD of 128 and 32. Explanation: Calculate the GCD of Two Numbers in C We may deduce from the examples above that the largest number that can divide both numbers is less than the smallest number that can divide both input numbers. As a result, we may create a naive method in which we test each number beginning with the lowest number between both the two integers and making our way up to 1. As a result, the will be whatever number comes first and entirely divides both input numbers. GCD of the two numbers Example: Input Numbers: N1 = 132 & N2 = 24 Smallest Number: N2 = 24 We will start a loop from 24 that will end at 1. We will then find the first number that will completely divide both numbers N1 and N2, in this case, it is 12. So the GCD of N1 and N2 will be 12. Algorithm of the above approach to find GCD: Declare two variables num1 and num2. Initialize both variables. Find the minimum number between both the number and store it in a different variable(minNum). Start a loop from minNum to 1. Now check if the num1 and num2 are divisible by the current iterating number and then store the result of it in another variable and come out of the loop. If they are not divisible then continue the same step. Print the result. C Program of the above algorithm { } { } } } #include <stdio.h> int main() int num 1 , num 2 , i; // Accepting and storing input of two numbers from user printf ( "Enter two numbers: " ); scanf ( "%d " , &num 1 ); scanf ( "%d " , &num 2 ); int minNum= 0 ; int result = 1 ; // Calculating smallest number among num 1 and num 2 if (num 1 <num 2 ){ minNum = num 1 ; } else { minNum = num 2 ; // loop from minNum to 1 for ( i = minNum; i > 1 ; --i ) // check if both num 1 and num 2 is divisible by i or not // store the outcome and break out of the loop if (num 1 %i == 0 && num 2 %i == 0 ){ result = i; break ; // Print the result printf ( "GCD of %d and %d is %d" , num 1 , num 2 , result); return 0 ; You can run this code on . Interviewbit 132, 24 Input: GCD of 132 and 24 is 12. Output: The smallest number among 132 and 24 is 24 so the loop starts from 24 and checks if 132 and 24 are divisible by 24 or not since both are not divisible so the loop will continue to run and now it will check for 23 and so on until the loop reaches to 12 where both numbers will be divisible by 12 so it will store the result and break out of the loop and then print the result. Explanation: Since the loop is running for the smallest number(n) to 1 so the time complexity will be O(n). Time Complexity: It's not taking any extra space other than some variables which are unrelated to the input so the space complexity of this algorithm will be O(1). Space Complexity: We can reduce the time complexity of this algorithm by using an efficient approach. Efficient Approach: Euclidean Algorithm The following facts serve as the foundation for the algorithm: GCD does not change when we subtract a smaller number from a bigger number (we reduce a larger number). So, if we continue to subtract the larger two values, we obtain GCD. Instead of subtracting, divide the smaller integer, and the procedure will terminate when we discover the remainder 0. We may begin by determining the lowest integer between 2 and using that number as the divisor. The greatest component will be our dividend. Then we divide it till the remainder reaches zero. If the remainder exceeds zero. The remainder will then become a divisor, and the current divisor will become a dividend. And must be repeated till the remainder equals zero. Given two numbers: N1=132, N2=24. See the following image for a better understanding Example: In the figure above, we divide the integer till we receive a residual of 0. When the remainder equals zero, the current divisor is the GCD. Algorithm of this Approach: Define a function that takes two arguments divisor and dividend. Now in the function check if the divisor divides the dividend entirely or not. Return the divisor if it divides it entirely otherwise. Recursively invoke the function by supplying the divisor as the remainder of the divisor and dividend. In addition to the dividend as the current divisor. C program for the above algorithm { { } } { dividend = num1; dividend = num2; } divisor = num1; divisor = num2; } } #include <stdio.h> //Function to calculate GCD int gcd( int divisor, int dividend) //Calculating remainder int remainder = dividend % divisor; // Base condition // If remainder is 0 then divisor will be GCD if ( remainder == 0) return divisor; //Recursive call to find GCD return gcd( remainder, divisor); int main() int num1, num2; //Accepting and storing input of two numbers from user printf( "Enter two numbers: " ); scanf( "%d " , &num1); scanf( "%d " , &num2); int dividend, divisor; //dividend will be the number which is gretest among the input if (num1 > num2){ } else { //Divisor will be the number which is lowest among the input if (num1 < num2){ } else { //Calling function to calculate GCD int ans = gcd(divisor, dividend); // Print the result printf( "GCD of %d and %d is %d" , num1, num2, ans); return 0 ; You can run this code on . Interviewbit 132, 24 Input: GCD of 132 and 24 is 12. Output: O(log(min(num1,num2)) which is equivalent to O(log(n)). Time Complexity: O(1), no extra space is used other than some variables. Space Complexity: Conclusion: GCD (Greatest Common Divisor) is a mathematical tool that specifies the number that may divide both integers. We've seen the Java code that was utilized to implement the algorithm. We also comprehended the algorithm's analysis in order to assess how optimal the algorithm is. The best method for calculating the GCD of two integers (Euclid's Algorithm) significantly reduces complexity during competitive programming.
