C Program to compute the GCD (HCF) of two numbers/*This program finds out the GCD of two numbers with and without using recursion. The method using recursion for finding the GCD was given by EUCLID and one can read more about EULICD's algorithm. */ #include<stdio.h> #include<conio.h> int num1,num2; int Recursiveapproach(int copy1,int copy2);//recursive function which return the GCD of two numbers void NonRecursiveapproach(int copy1,int copy2);//non recursive function int main() { int gcd; printf("This programs demonstrate GCD calculation using recursive and non-recursive approach\n"); printf("\nEnter first number\n"); scanf("%d",&num1); printf("\nEnter second number\n"); scanf("%d",&num2); if(num1>num2)//Our first parameter is the larger of the two numbers gcd=Recursiveapproach(num1,num2); else gcd=Recursiveapproach(num2,num1); printf("The GCD calculated using recursive approach is %d\n",gcd); NonRecursiveapproach(num1,num2); getch(); return 0; } int Recursiveapproach(int copy1,int copy2) {/*In the recursive method the larger number is divided by the smaller number ,the remainder is checked and then another call is made with paramters as smaller number and the remainder*/ if(copy2==0)//when the rmainder passed is zero than we have GCD as the smaller number passed(wiz copy1) return copy1; else Recursiveapproach(copy2,copy1%copy2); } void NonRecursiveapproach(int copy1,int copy2) { int div=2;//We divide both the numbers with div. We use the prime factorisation method. int gcd=1;//Initialise the GCD as 1 while(!(copy1==1||copy2==1||div>copy1||div>copy2)) { if((copy1%div==0)&&(copy2%div==0)) {//If both the numbers are divisible by div then divide and multiply div to the gcd gcd=gcd*div; copy1=copy1/div; copy2=copy2/div; } else//Otherwise divide the number which is divisible by div if((copy1%div==0)&&(copy2%div!=0)) copy1=copy1/div; else if((copy1%div!=0)&&(copy2%div==0)) copy2=copy2/div; else if((copy1%div!=0)&&(copy2%div!=0)) div++;//else increment div } printf("The GCD calculated without using recursion is %d",gcd); } /*A sample run of the program was carried out and the results were found as:- This programs demonstrate GCD calculation using recursive and non-recursive approach Enter first number 45 Enter second number 36 The GCD calculated using recursive approach is 9 The GCD calculated without using recursion is 9 */ |
Computer Science >