eulers totient Algorithm
Euler's Totient Algorithm, also known as Euler's Totient Function, is a mathematical algorithm that calculates the number of positive integers less than or equal to a given integer n that are relatively prime to n. In other words, it computes the count of numbers that share no common factors with the given number, except for 1. The function is named after the Swiss mathematician Leonhard Euler, who introduced it in the 18th century. It is denoted by φ(n) or ϕ(n) and plays a critical role in number theory, cryptographic systems, and the study of multiplicative functions.
The algorithm for calculating Euler's Totient Function is based on the property that the function is multiplicative, meaning that if two numbers are coprime (have no common factors other than 1), then the function of their product is the product of their individual functions. The algorithm involves factoring the given number into its distinct prime factors and applying the formula φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk), where p1, p2, ..., pk are the distinct prime factors of n. For example, φ(12) would be calculated as 12 * (1 - 1/2) * (1 - 1/3) = 12 * (1/2) * (2/3) = 4, since the prime factors of 12 are 2 and 3. This algorithm allows for efficient computation of the Euler's Totient Function, which is essential in various applications, such as the RSA encryption algorithm.
# Eulers Totient function finds the number of relative primes of a number n from 1 to n
def totient(n: int) -> list:
is_prime = [True for i in range(n + 1)]
totients = [i - 1 for i in range(n + 1)]
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for j in range(0, len(primes)):
if i * primes[j] >= n:
break
is_prime[i * primes[j]] = False
if i % primes[j] == 0:
totients[i * primes[j]] = totients[i] * primes[j]
break
totients[i * primes[j]] = totients[i] * (primes[j] - 1)
return totients
def test_totient() -> None:
"""
>>> n = 10
>>> totient_calculation = totient(n)
>>> for i in range(1, n):
... print(f"{i} has {totient_calculation[i]} relative primes.")
1 has 0 relative primes.
2 has 1 relative primes.
3 has 2 relative primes.
4 has 2 relative primes.
5 has 4 relative primes.
6 has 2 relative primes.
7 has 6 relative primes.
8 has 4 relative primes.
9 has 6 relative primes.
"""
pass
if __name__ == "__main__":
import doctest
doctest.testmod()
