Euler totient sieve in Python
Compute phi(m) for all m up to n. Start with phi[m] = m, and for each prime p subtract phi[m]/p from every multiple m of p. It takes Θ(n log log n) word operations and n + 1 words.
- File
euler_phi_sieve.py, 16 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/euler-phi-sieve/. The authors are listed in prov/1P82VA.jsonl.
def euler_phi_sieve(n: int) -> list[int]:
"""Return the list phi[0 .. n] with phi[m] = Euler's totient of m for m >= 1, and phi[0] = 0.
Precondition: n >= 0.
Cost: Theta(n log log n) word operations; the output list is the only table.
"""
phi = list(range(n + 1)) # @line L1
for p in range(2, n + 1): # @line L2
if phi[p] == p: # @line L3
for m in range(p, n + 1, p): # @line L4
phi[m] -= phi[m] // p # @line L5
return phi # @line L6
test_euler_phi_sieve.py 62 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/euler-phi-sieve/. The authors are listed in prov/1P82VA.jsonl.
import random
from math import gcd
from euler_phi_sieve import euler_phi_sieve
def phi_by_definition(m: int) -> int:
return sum(1 for j in range(1, m + 1) if gcd(j, m) == 1)
def phi_by_trial_division(m: int) -> int:
result, rest, d = m, m, 2
while d * d <= rest:
if rest % d == 0:
result -= result // d
while rest % d == 0:
rest //= d
d += 1
if rest > 1:
result -= result // rest
return result
def test_example() -> None:
assert euler_phi_sieve(12) == [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4]
def test_edges() -> None:
assert euler_phi_sieve(0) == [0]
assert euler_phi_sieve(1) == [0, 1]
assert euler_phi_sieve(2) == [0, 1, 1]
assert euler_phi_sieve(3) == [0, 1, 1, 2]
def test_against_definition_up_to_600() -> None:
table = euler_phi_sieve(600)
for m in range(1, 601):
assert table[m] == phi_by_definition(m)
def test_every_n_up_to_2000() -> None:
full = [0] + [phi_by_trial_division(m) for m in range(1, 2001)]
for n in range(2001):
assert euler_phi_sieve(n) == full[: n + 1]
def test_random_larger_n() -> None:
rng = random.Random(1763)
for _ in range(5):
n = rng.randint(2001, 60000)
table = euler_phi_sieve(n)
assert len(table) == n + 1
for m in rng.sample(range(1, n + 1), 300):
assert table[m] == phi_by_trial_division(m)
assert table[n] == phi_by_trial_division(n)
def test_sum_of_totients() -> None:
assert sum(euler_phi_sieve(1000)) == 304192
What the next level needs
- the tests did not run in this build