C Program To Find The GCD And LCM Of Two Numbers

The acronym GCD represents the Greatest Common Divisor. It refers to the largest positive integer that divides a set of positive numbers without any remainder.

The highest common factor (HCF), also referred to as the greatest common divisor (GCD) or the greatest common factor (GCF), is a mathematical concept used to determine the largest positive integer that divides two given integers. It is a crucial tool for comparing and analyzing integer values.

The greatest common divisor (GCD) is commonly computed for a pair of numbers in order to simplify fractions. Coprime or mutually prime numbers are those where the GCD of the two numbers is 1.

Steps to find GCD:

Use the following steps to find the GCD:

• ✅ The factors of the positive integer "m" should be written.
• ✅ List the factors that make up the positive integer "n" .
• ✅ Find the common divisors for "m" and "n" .
• ✅ Find the m and n common divisor whose biggest value you can divide by.

Example:

• ✅ Factors of 15: 1, 3, 5, 15 .
• ✅ Factors of 18: 1, 2, 3, 6, 9 , and 18 .
• ✅ 1,3 is the common factor between 15 and 18 .
• ✅ C.D. for 15 and 18 is 3 .

LCM - Least Common Multiple

The least common multiple (LCM) of two integers a and b is the smallest positive integer that can be evenly divided by both a and b. This calculation establishes that the smallest positive number is a multiple of at least two other numbers.

Steps to find LCM:

Use the following steps to find the LCM :

• ✅ Choose the two numbers: Call them num1 and num2 .
• ✅ Search for the largest common divisor (GCD): Use an algorithm like the Euclidean one to determine the GCD of the two numbers.
• ✅ Utilize the LCM formula: After obtaining the GCD , you may determine the LCM by using the formula below:

(num1 + num2) / GCD LCM

Example:

• ✅ Write the multiples of 4 and 6
• ✅ 4: 4,8,12,16,20,24,28,…..
• ✅ 6: 6,12,18,24,30,36,42…..

The previous two declarations indicate that the multiples of 4 and 6 are 12 and 24 respectively. If we extend this pattern further, additional similarities may emerge. As of now, 12 stands as the smallest common multiple for the numbers 4 and 6. Consequently, the least common multiple (LCM) of 4 and 6 remains 12.

Relation between GCD and LCM

The highest common factor (HCF) of the given numbers represents a set of two or more numbers. The smallest common multiple of two or more numbers is the least number among all the common multiples of those numbers. The formula for determining the connection between the least common multiple (LCM) and highest common factor (HCF) of a and b, where a and b are two numbers, can be expressed as:

LCM (a, b) × GCD (a, b) = a × b

Example:

Here is a C program that calculates the greatest common divisor (gcd) and least common multiple (lcm) of two numbers.

#include<stdio.h>

 int main()

 {

     int number_1, number_2, i, gcd, lcm;

printf("Enter the first number: ");

scanf("%d", &number_1);

printf("Enter the second number: ");

scanf("%d", &number_2);

for(i=1; i<=number_1 &&i<=number_2; i++)

     {

if(number_1%i==0 && number_2%i==0)

gcd=i;

     }

     lcm=(number_1*number_2)/gcd;

printf("GCD of %d and %d is  = %d\n",number_1,number_2,gcd);

printf("LCM of %d and %d is  = %d\n",number_1,number_2,lcm);

     return 0;

 }

Output:

Enter the first number: 15

Enter the second number: 18

GCD of 15 and 18 is  = 3

LCM of 15 and 18 is  = 90

Explanation:

• ✅ #include<stdio.h>: It contains the input/output library in the program.
• ✅ The main function's opening int statement .
• ✅ Located within the main function : Integer variables number1, number2 (input numbers), i (loop variable), gcd (greatest common divisor), and lcm (least common multiple) are declared by the statement int number1, number2 gcd lcm. Uses the syntax printf("Enter the first number: "); to display a message asking the user to enter the first number. Reads an integer from the user and assigns it to number1 with the function scanf("%d", &number1) . Uses the syntax printf("Enter the second number: "); to display a message asking the user to enter the second number. The user's next integer input is read and assigned to number2 by the function scanf("%d", &number2) . A for loop that goes from 1 to the smaller of the two input numbers (number1 and number2) is called for(i=1; i=number1 &&i=number2; i++) . The for loop contains: If both number1%i==0 and number2%i==0 , then determine whether the current value of i is a factor that both number1 and number2 lcm=(number1number2)/gcd;: Updates the gcd variable with the current value of i if true . uses the previously determined GCD to calculate the LCM. Calculates the LCM using the previously determined GCD by using the formula lcm=(number1number2)/gcd . The printf function displays the GCD of the two input numbers with the message "GCD of%dand%d is =%dn" . This command prints the LCM of the two input numbers: printf("LCM of%dand%d is =%dn", number1, number2, lcm); .
• ✅ return 0;: returns 0 to indicate that the operating system has received a successful report from the program.
• ✅ Integer variables number1, number2 (input numbers), i (loop variable), gcd (greatest common divisor), and lcm (least common multiple) are declared by the statement int number1, number2 gcd lcm.
• ✅ Uses the syntax printf("Enter the first number: "); to display a message asking the user to enter the first number.
• ✅ Reads an integer from the user and assigns it to number1 with the function scanf("%d", &number1) .
• ✅ Uses the syntax printf("Enter the second number: "); to display a message asking the user to enter the second number.
• ✅ The user's next integer input is read and assigned to number2 by the function scanf("%d", &number2) .
• ✅ A for loop that goes from 1 to the smaller of the two input numbers (number1 and number2) is called for(i=1; i=number1 &&i=number2; i++) .
• ✅ The for loop contains: If both number1%i==0 and number2%i==0 , then determine whether the current value of i is a factor that both number1 and number2 lcm=(number1*number2)/gcd;: Updates the gcd variable with the current value of i if true . uses the previously determined GCD to calculate the LCM.
• ✅ Calculates the LCM using the previously determined GCD by using the formula lcm=(number1*number2)/gcd .
• ✅ The printf function displays the GCD of the two input numbers with the message "GCD of%dand%d is =%dn" .
• ✅ This command prints the LCM of the two input numbers: printf("LCM of%dand%d is =%dn", number1, number2, lcm); .
• ✅ If both number1%i==0 and number2%i==0 , then determine whether the current value of i is a factor that both number1 and number2
• ✅ lcm=(number1*number2)/gcd;: Updates the gcd variable with the current value of i if true . uses the previously determined GCD to calculate the LCM.