Euler's Totient

Problem

Return Euler's totient of n: the count of integers from 1 through n that are coprime with n, with phi(1) = 1.

Factor n by trial division and multiply the running result by one minus one over each distinct prime using integer arithmetic. Return 0 for n <= 0.

Hint

For every distinct prime p dividing n, throw away result // p of the remaining count.

case 1

in: [1]

expected: 1

case 2

in: [9]

expected: 6

case 3

in: [10]

expected: 4

case 4

in: [36]

expected: 12

case 5

in: [97]

expected: 96

Starter codePython

def euler_phi(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor