Skip to main content

Euclid's Division Lemma - Program

Hello Everyone, how y'all are fine.

In this blog, we are gonna try to build program for Euclid's Division Lemma.

It just a mathematical theorem that states that "Given positive integers a and b, there exist unique integers q and r such that a = bq +r, 0< r < b".

Here basically 'a' is dividend, 'b' is divisor, 'q' is quotient and 'r' is remainder.

This is user to find the HCF(Highest Common Factor) of two numbers.

We are going to build program to do exactly that.

I am using C programming language, however this can be done using any programming language.

So I created a new C program file using vim and I used the below code.

  



=======
Code
=======

#include <stdio.h>

void main(){
        int num1,num2,a,b,q,r;
        printf("Enter a number: ");
        scanf("%d",&num1);
        printf("Enter another number: ");
        scanf("%d",&num2);
        if(num1>num2){
                b = num1;
                r = num2;
        }else{
                b = num2;
                r = num1;
        }
        do{
                a = b;
                b = r;
                q = a/b;
                r = a%b;
                printf("%d = (%d*%d)+%d\n",a,b,q,r);
        }while(r !=0);
        printf("HCF is %d\n",b);
}

========================================

If you see carefully, initially I stored the values in b and r instead of a and b. This is because as we enter the loop, we assign the value of b to a and r to b which needs to be done from the second iteration. We can assign the values to a and b at first and have condition to assign the value of b to a and r to b from second iteration, however that would require more lines of code. Kindly note that this code may not be the best approach to solve this problem, however it is the approach that I took to solve this. 

Once done, it's time to compile and test the code.


 So, we have compiled and tested the code and it looks to be running fine.

That's all for this blog, thanks for reading and have a wonderful day ahead.

Comments

Post a Comment

Popular posts from this blog

Swap two numbers without using a temporary variable

It's been a while since I've posted any blogs and vlogs. I've been trying to record videos for Planet of Codes Youtube channel, but there's quite a lot of noise whenever I try to record, so I thought why not I communicate through these blogs instead till I am able to record something for Youtube. So here we are, blogging for something that I actually tried to record in the form of a video. Usually in high schools and colleges, when most of us initially learn programming, we get a programming problem to swap two numbers. Usually the solution looks something like the below. num1 = 32 num2 = 87 temp = num1 num1 = num2 num2 = temp print(num1) print(num2) Note: Usually institutions ask students to write this program in C or C++ in first semester, however the above program is in Python, because, It's the logic that matters. This program can be written in any other programming language too. Well, here we are using a temporary variable "temp".  This problem can ac...
Post a Comment
Read more

Significance of Development and Production Environment for any Application

The concept of the environment that any application runs on was something that I was unaware of as a student. I got introduced to these concept after becoming a part of corporate IT sector. Two of the most important environment are Development environment and Production environment. Of course, there are testing environments like  OAT and UAT environment, but at times these are taken as a sub part of the above mentioned major environments. So now the question arises, "What are  these environment? and why do I need to know about these?". Well, although subconsciously, we all are aware of these, not all of us are aware of how important these are to us and to each other. Development environment is basically the environment where the application is developed and maintained. Any changes that needs to be made to any application are made in development environment as well. The application in development environment could be any application made from scratch or any third party applica...
Post a Comment
Read more

Project Narutopedia Webscraper

Hello Guys, It's been a while since I have posted something, isn't it?  So, what's up you ask? Well, it happened on Monday, 22nd February, 2021. I was just passing my time, watching a Youtube video on a virtual assistant project. The video was quite impressive to be honest. They even used some package to extract data from Wikipedia. After watching that video, I thought to myself, is there any such package for Narutopedia? Now those of you who know me personally, know how big of a Naruto and Boruto fan I am, so I started to check if I could find one, however, I couldn't find any. I am not saying that there is no Python package for Narutopedia, there could be one, it's just that I couldn't find any. So I thought, "Why not make a simple app that can extract data from Narutopedia for anything we search?". The only problem back then was that I had no idea how to do that. I then started to research and it took only a few minutes until I realized that there i...
Post a Comment
Read more