Euler\'s Totient function (or Euler\'s Phi function) is a function that accepts

Question

Euler's Totient function (or Euler's Phi function) is a function that accepts a positive integer n and returns how many positive integers less than n are relatively prime to n. at is, they have greatest common divisor of 1 with n As an example, consider computing p(12). We can see from the following table that only 1, 5, 7, and 11 are relatively prime to 12, so b(12) 4. gcd(r, 12) 10 11 The naive EulerPhi algorithm below computes Euler's Phi recursively based on the following recurrence if n is prime or 1 (b) gcd (a,b where a is a factor of n and b n/a 52, $(gcd(a,b)

Explanation / Answer

Answer for Question :

Example code for sentinel value:
Here sentinel value is -1,
printf(“enter sentinel value, -1 to end: “);
scanf(“%d”, &sentinel);
while (sentinel != -1)
{...
   printf(“enter sentinel value, -1 to end: “);
   scanf(“%d”, &sentinel);
}

Based on gcd computation value we can use either -1, 0

Answer for Question :

A technique used to avoid repeated calculations in
recursive functions
High-level idea: take a note (memo) of the return value of
a function call. When the function is called with the same
argument again, return the stored result
Each subproblem is solved at most once
Some may not be solved at all!

map<int,int>memo;

Input: n: positive integer
output: phi(n)

Algorithm: EulerPhi
if(memo.count(n)) return memo[n];
for a = 2 to [sqrt[n]] do
   if a divides n then
   b = n/a;
   g = gcd(a,b)
   return memo[n] = EulerPhi(a) . EulerPhi(b) . g/EulerPhi(g)
   end
end
return n-1

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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