Program to find LCM and HCF of two numbers without using Loops in C

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 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 :

function gcd(a, b)
    if b = 0
       return a; 
    else
       return gcd(b, a mod b);

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 :)

Program to find LCM and HCF of two numbers using loops in C

Hi Friends,
     Before wirting the program, I will tell you what is LCM (Lowest Common Multiple) and HCF (Highest Common Factor). If you already know what is LCM and HCF then you can skip the theory and redirect to program.

HCF is the highest positive number that divides all given number for which you are calculating HCF. It is multiplication of common factor of given numbers. i.e.

90 = 1 * 2 * 3 * 3 * 5
70 = 1 * 2 * 5 * 7

Hence the HCF of 90 and 70 will be 1 * 2 * 5 = 10

LCM is the smallest positive number that can be divided by all the given numbers. It is the least common multiple of given numbers. i.e.

90 = 90 , 180 , 270 , 360 , 450 , 540, 630 ,720 , 810 , 900 , 990 ..... ..... .... ....
70 = 70 , 140 , 210 , 280 , 350 , 420, 490, 560 , 630 , 700 , 770 .... .... .... .....

Hence the LCM of 90 and 70 will be 63.

/*
     Program to implement LCM , HCF using loops
     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){
    int temp;
    while(b != 0){
        temp = b;
        b = a % b;
        a = temp;
    }
    return temp;
}
int lcm(int a, int b){
    int temp;
    temp = a > b ? a : b;
    while(1){
        if(temp % a == 0 && temp % b == 0){
            return temp;
        }
        temp++;
    }
}

Output :

Enjoy :)

Program to create Simple Binary Tree with recursive traversal

/*
    Simple Binary Tree with recursive traversal
    Created By : Pirate
*/

/*Create the simple binary tree and recursive traversal*/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>

typedef struct tree{
    int data;
    struct tree *left;
    struct tree *right;
}node;

void insert (node *, node*);
void inorder (node *);
void preorder (node *);
void postorder (node *);
node *get_node();

int main(){
    int choice;
    char ans = 'n';
    node *newNode,*root;
    root = NULL;
    do{
        printf("*** Simple Binary Tree ***\n");
        printf("\n1.Create\n");
        printf("2.Inorder\n");
        printf("3.Preorder\n");
        printf("4.Postorder\n");
        printf("5.Exit\n");
        printf("Enter Your choice: ");
        scanf("%d",&choice);
        switch(choice){
            case 1:
                root = NULL;
                do{
                    newNode=get_node();
                    printf("Enter the Element\n");
                    scanf("%d",& newNode->data);
                    if(root == NULL)
                        root= newNode;
                    else
                        insert(root, newNode);
                    printf("\nDo you want to enter more elements?(Y/N)\n");
                    ans = getch();
                }while(ans== 'Y'|| ans=='y');
                break;
            case 2:
                if(root == NULL)
                    printf("Tree is not created!");
                else
                    inorder(root);
                break;
            case 3:
                if(root ==NULL)
                    printf("Tree is not created!");
                preorder (root);
                break;
            case 4:
                if(root == NULL)
                    printf("Tree is not created!");
                postorder(root);
                break;
        }
    }while(choice!=5);
    return 0;
}
node *get_node(){
    node *temp;
    temp = (node *) malloc(sizeof(node));
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
void insert(node *root, node *newNode){
    char ch;
    printf("Where to insert left (L)/right (R) of %d:\n", root->data);
    ch=getche();
    if((ch=='R') || (ch=='r')){
        if(root->right == NULL){
            root->right=newNode;
        }
        else
            insert(root->right,newNode);
        }
    else{
        if(root->left== NULL){
            root->left=newNode;
        }
        else
            insert(root->left,newNode);
    }
}
void inorder(node *temp){
    if(temp!= NULL){
        inorder(temp->left);
        printf("%d\n", temp->data);
        inorder(temp ->right);
    }
}
void preorder(node *temp){
    if(temp != NULL){
        printf("%d\n",temp->data);
        preorder(temp->left);
        preorder(temp->right);
    }
}
void postorder(node *temp){
    if(temp!= NULL){
        postorder(temp-> left);
        postorder(temp->right);
        printf("%d\n",temp->data);
    }
}

Output :

Enjoy :)