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