Lets write a C program to find GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of two positive integer numbers input by the user using Euclid’s Algorithm and by using Recursive function call logic.
If user inputs 2 numbers n1 and n2, reduce the bigger number by modulo dividing it by the smaller number. For example, if n1 is greater than n2, then reduce the value of n1 by replacing it with n1%n2.
Assume that we’ve a function gcd() which returns gcd of 2 numbers passed to it. Ex: gcd(n1, n2);
According to Euclid’s Algorithm, we’ll get the same gcd if we reduce the bigger number by modulo dividing it by smaller number.
If n1 > n2 we need to pass gcd(n1%n2, n2); If n2 > n1, we need to pass gcd(n1, n2%n1);
We need to recursively execute above 2 lines of logic until either n1 is 0 or until n2 is 0. If n1 is 0, then value present in n2 is the gcd of (n1,n2). If n2 is 0, then value present in n1 is the gcd of (n1,n2).
Video Tutorial: C Program To Find GCD of Two Numbers using Recursion: Euclid’s Algorithm
Output 2: Enter 2 positive integer numbers 1980 1617
Greatest Common Divisor of 1980 and 1617 is 33.
Logic To Find GCD using Repeated Subtraction
Lets assume that num1 = 15 and num2 = 20. Lets calculate GCD for these 2 numbers.
While loop iterates until num1 is equal to num2.
num1
num2
Greater No
Subtract Numbers
Result
15
20
num2 = 20
num2 = num2 – num1
num2: 20 – 15 = 5
15
5
num1 = 15
num1 = num1 – num2
num1: 15- 5 = 10
10
5
num1 = 10
num1 = num1 – num2
num1: 10- 5 = 5
5
5
Both Are Equal
num1 == num2
GCD is 5.
You can see below code in the C program i.e., converting a negative number into positive. Our source code above works only for positive integer numbers without this code. If the user enters negative value we use ternary operator to make it a positive value.
Here we check if num1 is less than 0. If true, then value of num1 is negative. So we multiply the number by -, which gives us a positive number. For example, if num1 is -15, then -(-15) is +15.
That would convert a negative number to positive number.
While Loop While loop iterates until num1 is not equal to num2. Once num1 is equal to num2, control exits while loop. Whatever is present in num1 or num2 is the GCD of 2 positive integer numbers entered by the user.
Inside while loop, we check if num1 is greater than num2. If true, we subtract num2 from num1 and store it back inside variable num1. Else if num2 is greater than num1, then we subtract num1 from num2 and store it back inside num2. We repeat this until num1 is equal to num2.
printf("\nGreatest Common Divisor of %d and %d is %d.\n", j, k, gcd);
return 0;
}
void calc_gcd(int numerator, int denominator, int *gcd)
{
int temp, num;
if(denominator == 0)
{
*gcd = numerator;
}
elseif(numerator == 0)
{
*gcd = denominator;
}
else
{
num = numerator / denominator;
temp = numerator - num * denominator;
while(temp)
{
numerator = denominator;
denominator = temp;
num = numerator / denominator;
temp = numerator - num * denominator;
}
*gcd = denominator;
}
}
#include<stdio.h>
void calc_gcd(int, int, int*);
int main()
{
int j, k, gcd;
printf("Enter 2 integer numbers\n");
scanf("%d%d", &j, &k);
calc_gcd(j, k, &gcd);
printf("\nGreatest Common Divisor of %d and %d is %d.\n", j, k, gcd);
return 0;
}
void calc_gcd(int numerator, int denominator, int *gcd)
{
int temp, num;
if(denominator == 0)
{
*gcd = numerator;
}
else if(numerator == 0)
{
*gcd = denominator;
}
else
{
num = numerator / denominator;
temp = numerator - num * denominator;
while(temp)
{
numerator = denominator;
denominator = temp;
num = numerator / denominator;
temp = numerator - num * denominator;
}
*gcd = denominator;
}
}
Output 1: Enter 2 integer numbers 1980 1617
Greatest Common Divisor of 1980 and 1617 is 33.
Output 2: Enter 2 integer numbers 1617 1980
Greatest Common Divisor of 1617 and 1980 is 33.
Output 3: Enter 2 integer numbers 15 20
Greatest Common Divisor of 15 and 20 is 5.
Output 4: Enter 2 integer numbers 20 15
Greatest Common Divisor of 20 and 15 is 5.
Logic To Find GCD using Pointers and Functions, using Euclid’s Algorithm
We ask the user to input integer values for variables j and k. We pass values of j and k and address of variable gcd to a function called calc_gcd().
Inside calc_gcd() function Inside calc_gcd() function we use the following calculations:
Note: We copy the value of j, k and &gcd passed by main method into local variables of calc_gcd() i.e., numerator, denominator and *gcd.
Step 1: We check if denominator is 0. In that case the value present in numerator itself is the GCD. So we copy value present in variable numerator to *gcd.
Step 2: If denominator is not zero. Then, we divide numerator with denominator value and store the result into a variable called num.
num = numerator / denominator;
If j = 1980 and k = 1617, then numerator = 1980 and denominator = 1617.
num = numerator / denominator; num = 1980/ 1617; num = 1;
According to problem statement:
1980 / 1617 = 1
1980 – 1 * 1617 = 363
We’ve formulated the equation for the first part i.e., 1980 / 1617 = 1 Now lets formulate an equation for the second part i.e., 1980 – 1 * 1617 = 363
If you look at 1980 – 1 * 1617 = 363 closely and substitute the values with corresponding variables then you’ll come up with below formula:
temp = numerator – num * denominator;
Look at Step 1 for values of numerator, denominator and num.
Now lets look at the equations given in the problem statement:
1980 / 1617 = 1
1980 – 1 * 1617 = 363
1617 / 363 = 4
1617 – 4 * 363 = 165
In this look at 1617 / 363 = 4. Here the value of denominator has been shifted to numerators place, and the value of temp has been copied to denominator. So lets write the code:
numerator = denominator; denominator = temp;
Step 3: Now lets use these formulate in co-ordination to finish writing our function code.
We need to repeat the code in order to get the results according to the columns present in the problem statement equations:
Here are our formulas:
num = numerator / denominator;
temp = numerator - num * denominator;
numerator = denominator;
denominator = temp;
num = numerator / denominator;
temp = numerator - num * denominator;
numerator = denominator;
denominator = temp;
Here are the steps in problem statement to calculate the GCD:
1980 / 1617 = 1
1980 – 1 * 1617 = 363
1617 / 363 = 4
1617 – 4 * 363 = 165
363 / 165 = 2
363 – 2 * 165 = 33
5 / 33 = 5
165 – 5 * 33 = 0
We need to repeat execution of our code to get above result:
num = numerator / denominator;
temp = numerator - num * denominator;
while(temp)
{
numerator = denominator;
denominator = temp;
num = numerator / denominator;
temp = numerator - num * denominator;
}
*gcd = denominator;
We need to put our code inside a looping construct to repeat the code. Here we are using while loop. So while loop iterates until temp value is positive. Once value of temp is 0, the control exits the while loop.
We have written 2 lines of code before the while loop:
num = numerator / denominator;
temp = numerator - num * denominator;
num = numerator / denominator;
temp = numerator - num * denominator;
that is because we need to have some value inside variable temp before using it as condition for while loop.
Once the value of temp is 0, control exits while loop. Outside while loop we transfer the value present inside denominator to *gcd.
So *gcd will have the Greatest Common Divisor for values input by the user(j = 1980 and k = 1617).
Observe this table from problem statement
1980 / 1617 = 1
1980 – 1 * 1617 = 363
1617 / 363 = 4
1617 – 4 * 363 = 165
363 / 165 = 2
363 – 2 * 165 = 33
5 / 33 = 5
165 – 5 * 33 = 0
When temp value is 0, value of denominator is 33 – which is the Greatest Common Divisor of numbers 1980 and 1617.
Lets write a C program to print N co-prime or relative prime numbers. N being the user entered limit for printing the co-prime number pairs.
Co-Prime numbers / Relative Prime Numbers: Two numbers are said to be co-prime or relative prime numbers if they do not have a common factor other than 1.
OR
Two numbers whose Greatest Common Divisor(GCD) is 1 are known as Co-Prime or Relative Prime Numbers.
Note: User entered numbers(to check for co-prime) do not require to be prime numbers.
Output 1: How many co-prime numbers you want to print? 10 1. ( 2, 3 ) are co-prime numbers. 2. ( 3, 4 ) are co-prime numbers. 3. ( 2, 5 ) are co-prime numbers. 4. ( 3, 5 ) are co-prime numbers. 5. ( 4, 5 ) are co-prime numbers. 6. ( 5, 6 ) are co-prime numbers. 7. ( 2, 7 ) are co-prime numbers. 8. ( 3, 7 ) are co-prime numbers. 9. ( 4, 7 ) are co-prime numbers. 10. ( 5, 7 ) are co-prime numbers.
Output 2: How many co-prime numbers you want to print? 14 1. ( 2, 3 ) are co-prime numbers. 2. ( 3, 4 ) are co-prime numbers. 3. ( 2, 5 ) are co-prime numbers. 4. ( 3, 5 ) are co-prime numbers. 5. ( 4, 5 ) are co-prime numbers. 6. ( 5, 6 ) are co-prime numbers. 7. ( 2, 7 ) are co-prime numbers. 8. ( 3, 7 ) are co-prime numbers. 9. ( 4, 7 ) are co-prime numbers. 10. ( 5, 7 ) are co-prime numbers. 11. ( 6, 7 ) are co-prime numbers. 12. ( 3, 8 ) are co-prime numbers. 13. ( 5, 8 ) are co-prime numbers. 14. ( 7, 8 ) are co-prime numbers.
Logic To Print N Co-Prime Numbers
User enters limit value i.e., how many co-prime numbers he or she wants to print. We put that limit inside while loop condition. So while loop code executes repeatedly until limit is not equal to 0. We decrement the value of limit by 1 as and when we print the co-prime numbers.
Inside while loop we write nested for loop. The outer for loop selects the values for num1 and num2. We know that the first co-prime or relative prime number is 2 and 3. So we initialize num1 = 2 and num2 = 3. We keep incrementing the value of num2 by one outside the outer for loop, and iterate the for loop until num1 is less than or equal to num2.
If num2 is 3, then for loop checks for (num1 always starts from 2, till num1 <= num2) – (2, 2), (3, 2).
Next num2 will be 4. So for loop checks for – (2, 4), (3, 4), (4, 4)
Next num2 will be 5. So for loop checks for – (2, 5), (3, 5), (3, 5), (4, 5) ..and so on.
Note: Since limit– is inside a for loop, even though limit becomes 0 the while loop won’t exit immediately, until the for loop completes its iterations. It avoid that, we make sure the value of num1 is assigned number greater than num2. That way control exits for loop. Since limit is 0, the control even exits while loop.
Lets write a C program to check whether two positive numbers entered by the user are Co-Prime numbers / Relative Prime Numbers or not using function / method.
Co-Prime numbers / Relative Prime Numbers: Two numbers are said to be co-prime or relative prime numbers if they do not have a common factor other than 1.
OR
Two numbers whose Greatest Common Divisor(GCD) is 1 are known as Co-Prime or Relative Prime Numbers.
Factors of a number: All the numbers which perfectly divide a given number are called as Factors of that number.
Note: User entered numbers(to check for co-prime) do not require to be prime numbers.
printf("%d and %d are co-prime numbers.\n", n1, n2);
}
else
{
printf("%d and %d are not co-prime numbers.\n", n1, n2);
}
return 0;
}
#include<stdio.h>
int coprime(int num1, int num2)
{
int min, count, flag = 1;
min = num1 < num2 ? num1 : num2;
for(count = 2; count <= min; count++)
{
if( num1 % count == 0 && num2 % count == 0 )
{
flag = 0;
break;
}
}
return(flag);
}
int main()
{
int n1, n2;
printf("Enter 2 positive numbers\n");
scanf("%d%d", &n1, &n2);
if( coprime(n1, n2) )
{
printf("%d and %d are co-prime numbers.\n", n1, n2);
}
else
{
printf("%d and %d are not co-prime numbers.\n", n1, n2);
}
return 0;
}
Output 1: Enter 2 positive numbers 8 15 8 and 15 are co-prime numbers.
Output 2: Enter 2 positive numbers 12 15 12 and 15 are not co-prime numbers.
Note: coprime() method returns 1 or 0 value. If it returns 1, then the code inside if block gets executed. If it returns 0, then the code inside else block gets executed.