c. In mathematics, the greatest common divisor (gcd) of two non-zero integers is

Question

c. In mathematics, the greatest common divisor (gcd) of two non-zero integers is the largest positive integer that divides each of the integers without a remainder. One way of finding the gcd of two different positive integers is to replace the largest value by the magnitude of their difference, stopping when both the numbers are the same, this final value is the GCD of the two original numbers. Write two algorithms (1) non-recursive and (2) recursive in pseudocode to output the gcd of any two different integers using the algorithm described above. Your algorithm must handle scenarios when a user enters non numeric or numbers less or equal to zero

Explanation / Answer

// GCD Recursive Function

Read p & q two number

Check IF p & q are integer, else show error message

Check IF ( p > 0 & q > 0) else show error message

Example: -

GCD(6,4)

Here 6!=4 so it will go in else part

If 6 > 4

So again GCD(6-4,4)

GCD(2,4)

Here 2!=4 so it will go in else part

If( 2 < 4 )

So again GCD(2,4-2)

GCD(2,2)

Here 2 = =2 so it will return 2

// GCD NON Recursive Function

Read p & q two number

Check IF p & q are integer, else show error message

Check IF ( p > 0 & q > 0) else show error message

FUNCTION GCD(int p, int q) {

while (p != q) {

         if (p > q)

            { p = p-q; }

         else

            { q = q-p; }

      }   

      return p;

   }

Example: -

GCD(6,4)

Here 6!=4 so it will go in else part

If 6 > 4

So p=2, q=4

Now 2 <4

Here 2!=4

So q= 4-2

P=2,q=2

Here 2 = = 2 so it will return 2

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

If you have any query, please feel free to ask.

Thanks a lot.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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