Wednesday 12 September 2012

To find the GCD of two given integers by using the non recursive function


Description:
GCD means Greatest Common Divisor. i.e the highest number which divides the given number
Ex: GCD(12,24) is 12
Formula: GCD= product of numbers/ LCM of numbers
Algorithm:
Step 1: start
Step 2: read a,b
Step 3: call sub program g=GCD(a,b)
Step 4: print the g value
Step 5: stop
           Sub program:
Step 1: initialize the p=1, q, remainder
Step 2: remainder=p-(p/q*q)
Step 3: remainder=0 return q else goto step 4
Step 4: GCD(q,remainder) return to main program
 
Program:
#include<stdio.h>
#include<conio.h>
#include<math.h>
int gcdnonrecursive(int m,int n)
{
            int remainder;
            remainder=m-(m/n*n);
             if(remainder==0)
            return n;
             else
             gcdnonrecursive(n,remainder);
}

void main()
{
             int a,b,igcd;
  clrscr();
             printf("enter the two numbers whose gcd is to be found:");
            scanf("%d%d",&a,&b);
            printf("GCD of %d",gcdnonrecursive(a,b));
                                     getch();
}
Output:
1. enter the two numbers whose gcd is to be found:5,25
     GCD of  a,b is : 5
2. enter the two numbers whose gcd is to be found:36,54
     GCD of  a,b is : 18
3. enter the two numbers whose gcd is to be found:11,13
     GCD of  a,b is : 1
Conclusion:
The program is error free

VIVA QUESATIONS:

1)What is meaning of GCD ?
Ans:
GCD means Greatest Common Divisor. i.e the highest number which divides the given number

No comments:

Post a Comment