Let RELPRIME = { | x and y are positive integers that are relatively prime}. Giv
ID: 3777650 • Letter: L
Question
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.
Explanation / Answer
#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
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.