forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy patheuler_totient.py
More file actions
40 lines (31 loc) · 837 Bytes
/
euler_totient.py
File metadata and controls
40 lines (31 loc) · 837 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
"""
Euler's Totient Function
Compute Euler's totient function phi(n), which counts the number of integers
from 1 to n inclusive that are coprime to n.
Reference: https://en.wikipedia.org/wiki/Euler%27s_totient_function
Complexity:
Time: O(sqrt(n))
Space: O(1)
"""
from __future__ import annotations
def euler_totient(n: int) -> int:
"""Compute Euler's totient function phi(n).
Args:
n: A positive integer.
Returns:
The count of integers in [1, n] coprime to n.
Examples:
>>> euler_totient(8)
4
>>> euler_totient(21)
12
"""
result = n
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
while n % i == 0:
n //= i
result -= result // i
if n > 1:
result -= result // n
return result