# # Variants of the sieve of Eratosthenes (Python) # by Project Nayuki, 2021. Public domain. # https://www.nayuki.io/page/the-versatile-sieve-of-eratosthenes # from typing import List # Given an integer limit, this returns a list of Booleans # where result[k] indicates whether k is a prime number. def sieve_primeness(limit: int) -> List[bool]: if limit < 0: raise ValueError("Limit must be non-negative") result: List[bool] = [True] * (limit + 1) result[0] = False if limit > 0: result[1] = False for i in range(2, len(result)): if result[i]: for j in range(i * i, len(result), i): result[j] = False return result # Given an integer limit, this returns a list of integers # where result[k] is the smallest prime factor of k. def sieve_smallest_prime_factor(limit: int) -> List[int]: if limit < 0: raise ValueError("Limit must be non-negative") result: List[int] = [0] * (limit + 1) if limit > 0: result[1] = 1 for i in range(2, len(result)): if result[i] == 0: result[i] = i for j in range(i * i, len(result), i): if result[j] == 0: result[j] = i return result # Given an integer limit, this returns a list of integers # where result[k] is the totient (Euler phi function) of k. def sieve_totient(limit: int) -> List[int]: if limit < 0: raise ValueError("Limit must be non-negative") result: List[int] = list(range(limit + 1)) for i in range(2, len(result)): if result[i] == i: for j in range(i, len(result), i): result[j] -= result[j] // i return result # Given an integer limit, this returns a list of integers where result[k] # is the number of unique prime factors (omega function) of k. def sieve_omega(limit: int) -> List[int]: if limit < 0: raise ValueError("Limit must be non-negative") result: List[int] = [0] * (limit + 1) for i in range(2, len(result)): if result[i] == 0: for j in range(i, len(result), i): result[j] += 1 return result # Given an integer limit, this returns a list of integers where result[k] # is the product of the unique prime factors (radical function) of k. def sieve_radical(limit: int) -> List[int]: if limit < 0: raise ValueError("Limit must be non-negative") result: List[int] = [1] * (limit + 1) result[0] = 0 for i in range(2, len(result)): if result[i] == 1: for j in range(i, len(result), i): result[j] *= i return result