Consider the following algorithm: The input will be any integer, n, greater than

Question

Consider the following algorithm: The input will be any integer, n, greater than 1.
step 1. set t = n - 1
step 2. if t divides n, then output t and stop
step 3. replace t by t - 1 and go to step 2
Hint: Recall that one integers divides another means the remainder is 0 when
the first is divided into the second. So, for example, 4 divides 12 but 4 does not
divide 18.
(a) List the steps the algorithm follows for the input n = 6.
(b) Describe in words what this algorithm does. In other words, what problem
does this algorithm solve?

Explanation / Answer

(a) Step 1: Set t=6-1=5 Step 2: 5 does not divide six, so Step 3: Replace 5 with 4. 4 does not divide 6, so replace four with 3. 3 does divide six, so we are done. Output t=3. (b) This algorithm finds the largest number t which evenly divides n, i.e. the largest number such that n/t has a remainder of 0.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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