1. The greatest common divisor of two non-negative integers i and jis the larges

Question

1. The greatest common divisor of two non-negative integers i and jis the largest integer that divides both i and j evenly. Forexample, gcd(24, 30) = 6, and gcd(24, 35) = 1. Write arecursive function that takes two integers i and j and finds theirgreatest common divisor.

void gcd(int num1, int num2, int *answer) which takes two integersi and j, and returns gcd(i,j) in *answer. Use the followingalgorithm. This algorithm only works when i > j. Remember the user might input values where i < j. Youralgorithm should handle that case too.

If j divides i evenly, then j is the GCD of i and j.

If j does not divide i evenly, let k be the remainder when i isdivided by j. Then gcd(i,j) is the same as gcd(j,k).

Start with the non-recursive version and make sure it works beforeventuring into the recursive version.

---------------------------------------------------------------------------------------------------------


2. Description: In this assignment, we find the
   GCD of two positive integers. We use Euclid'sclassic
   algorithm.

   Let M and N be two postive integers

   Step1 : Assign M and N the value of the larger
           andsmaller of the two input values
          respectively.

   Step 2: Divide M by N, and call the remainder R

   Step 3: If R is not 0, then assign M the value of
           N,assign N the value of R, and return to
           Step2. Otherwise, the greatest common divisor
           is thevalue currently assigned to N.

   In other words:
   if M % N is zero, N is the GCD of M and N
   Otherwise GCD(M, N) is GCD(N, M % N)

   Concepts used: pointers and recursion

   Known Bugs: Whatever bugs your program has
*/
void swap(int *a, int *b);
/* takes two integer values *a and *b and swaps them */

void gcd(int a, int b, int *answer);
/* finds the GCD of a and b and places the result in *answer*/

void getValues(int *a, int *b);
/* gets two integer values from the user and places them in*a and *b */


int main() {
}

void getValues(int *a, int *b) {
/* gets two integer values from the user and places them in*a and *b */
}

void swap(int *a, int *b) {
/* takes two integer values *a and *b and swaps them */
}

void gcd(int num1, int num2, int *answer) {
/* finds the GCD of a and b and places the result in*answer
    Uses the recursive version of GCD
*/
}

/* output:
[aparna@localhost Spring09]$ gcc -o Assg3 Assg3.c
[aparna@localhost Spring09]$ ./Assg3

Please enter two positive integers separated by a space: 20 30
The GCD of 20 and 30 is 10
Do you want to continue? Type Y for Yes and N for No: y

Please enter two positive integers separated by a space: 21 121
The GCD of 21 and 121 is 1
Do you want to continue? Type Y for Yes and N for No: y

Please enter two positive integers separated by a space: 55 165
The GCD of 55 and 165 is 55
Do you want to continue? Type Y for Yes and N for No: y

Please enter two positive integers separated by a space: 3 1024
The GCD of 3 and 1024 is 1
Do you want to continue? Type Y for Yes and N for No: y

Please enter two positive integers separated by a space: 0 56
The input numbers must be greater than 0
Do you want to continue? Type Y for Yes and N for No: y

Please enter two positive integers separated by a space: 0 0
The input numbers must be greater than 0
Do you want to continue? Type Y for Yes and N for No: y

Please enter two positive integers separated by a space: 24 144
The GCD of 24 and 144 is 24
Do you want to continue? Type Y for Yes and N for No: n

Explanation / Answer

# include<stdio.h>
#include <conio.h>
#include<ctype.h>
int gcd(int,int);
void swap(int*,int*);
int main()
{
   intnum1=0;       
   int num2=0;
   int val;
   int yorn;    
do{
   while(num1==0||num2==0)
     { printf("Please enter two positiveintegers separated by a space: ");
       scanf("%d %d",&num1,&num2);
       if(num1==0||num2==0)
            printf("The input numbers must be greater than 0 ");
       }
       if(num1>num2)
          swap(&num1,&num2);
       val=gcd(num1,num2);
       printf("The GCD of %d and %dis %d ",num1,num2,val);
       printf("Do you want tocontinue? Type y for Yes and n for No: ");
       num1=0;
       num2=0;
      yorn=getch();      
       putch(yorn);
       printf(" ");
      }while(toupper(yorn)=='Y');
  
  getch();                                     //use this, needs conio to be included
   return 0;
  
}
void swap(int *a,int*b)
    {int t;
      t=*a;
      *a=*b;
      *b=t;
     return;
     }
int gcd(int m, int n)     //Euclidsalgorithm
{     if(m%n==0)
          returnn;
      else
           returngcd(n,m%n);

}   

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.