Hi Friends,

In the previous blogpost you have seen that I have implemented the LCM and HCF using loops. Now I'm here to find out LCM and HCF without loops in which we will use recursion.

To implement it , I will use

I have used 70 and 90 in my last blogspot example. I'm going to use same numbers here.

Let's write the program.

/*

Program to implement LCM , HCF using

Created By : Pirate

*/

#include<stdio.h>

#include<conio.h>

int hcf(int a,int b);

int lcm(int a,int b);

int main(){

int number_a,number_b;

printf("Enter the two no\n");

scanf("%d%d",&number_a,&number_b);

printf("\nHighest Common Factor HCF is %d\n", hcf(number_a,number_b));

printf("\nLowest Common Multiple LCM is %d", lcm(number_a,number_b));

return 0;

}

int hcf(int a, int b){

if(a==0){

return b;

}else{

return(hcf(b%a,a));

}

}

int lcm(int a,int b){

int temp;

temp = hcf(a,b);

return (a * b) / temp;

}

In the previous blogpost you have seen that I have implemented the LCM and HCF using loops. Now I'm here to find out LCM and HCF without loops in which we will use recursion.

To implement it , I will use

**Euclidean algorithm.**

In mathematics, the Euclidean algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements.

**-****Wikipedia**

__Algorithm :__functiongcd(a, b)ifb = 0returna;elsereturngcd(b, amodb);

**HCF :**I will calculate HCF using Eulidean algorithm.**LCM :**As we know that if we know the**HCF**of any two numbers we can easily find out**LCM**by using below**formula**.**LCM = (Number1 * Number2) / HCF**I have used 70 and 90 in my last blogspot example. I'm going to use same numbers here.

**HCF**= 10 (Calculated by Algorithm).**LCM**= (70 * 90 ) / 10 = 630.Let's write the program.

/*

Program to implement LCM , HCF using

**Euclidean**Algorithm.Created By : Pirate

*/

#include<stdio.h>

#include<conio.h>

int hcf(int a,int b);

int lcm(int a,int b);

int main(){

int number_a,number_b;

printf("Enter the two no\n");

scanf("%d%d",&number_a,&number_b);

printf("\nHighest Common Factor HCF is %d\n", hcf(number_a,number_b));

printf("\nLowest Common Multiple LCM is %d", lcm(number_a,number_b));

return 0;

}

int hcf(int a, int b){

if(a==0){

return b;

}else{

return(hcf(b%a,a));

}

}

int lcm(int a,int b){

int temp;

temp = hcf(a,b);

return (a * b) / temp;

}

__Output :__

**Enjoy :)**

## 0 comments:

## Post a Comment