Let RELPRIME x and y are positive integers that are relat

Let RELPRIME = { | x and y are positive integers that are relatively prime}. Given the following algorithm to test if two positive integers are relatively prime, let n be the maximum number of decimal digits in x and y. Analyze the running time of this algorithm, using O-notation. Explain the details and give your reasoning for each step.

On input where x and y are positive integers.

1. Repeat until y = 0:

2. Assign x x mod y.

3. Swap x and y.

4. Output x. If the result is 1, accept; otherwise reject.

Solution

#include<stdio.h>
int main()
{
int x, y, t;
//Accepts 2 numbers
printf(\"\ Enter 2 numbers: \");
scanf(\"%d%d\", &x, &y);
//Repeats till y is not zero
while(y != 0)
{
//Find out the remainder
x = x % y;
//Swaps the numbers
t = x;
x = y;
y = t;
}
if(x == 1)
printf(\"\ Result = %d\", x);
}

Output 1:

Enter 2 numbers: 7 5

Accepted Result = 1

Output 2:

Enter 2 numbers: 13 25

Accepted Result = 1

Output 3:

Enter 2 numbers: 12 15

Rejected Result = 3