Euler’s totient function, also known as φ function, can only be positive integers. Definition is the number of numbers that are mutually pure with N in N numbers from 1 to N. There is no general formula for Euler's function, only segmented recursive formulas. Here are the Euler function values from 1 to 10:
| x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| φ(x) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 |
The simplest algorithm for Euler's function is looping. But this calculation method is very time-consuming. Gauss proved the following formula:
∑
d
∣
n
ϕ
(
d
)
=
n
\sum_{d|n}\phi(d)=n
d∣n∑ϕ(d)=n
Here d|n means traversing all divisors of n. For example, all divisors of 10 are 1, 2, 5, 10. This formula has no appropriate translation, I will translate it as the sum of the divisor Euler functions. Therefore, the above formula is used:
ϕ
(
1
)
+
ϕ
(
2
)
+
ϕ
(
5
)
+
ϕ
(
10
)
=
10
\phi(1)+\phi(2)+\phi(5)+\phi(10)=10
ϕ(1)+ϕ(2)+ϕ(5)+ϕ(10)=10
After verification, it is indeed correct:
ϕ
(
1
)
+
ϕ
(
2
)
+
ϕ
(
5
)
+
ϕ
(
10
)
=
1
+
1
+
4
+
4
=
10
\phi(1)+\phi(2)+\phi(5)+\phi(10)=1+1+4+4=10
ϕ(1)+ϕ(2)+ϕ(5)+ϕ(10)=1+1+4+4=10
But after understanding this formula, we can use a fast algorithm to calculate. However, the calculation process cannot be understood immediately, so I took the φ(10) just now as an example. Let me explain in detail:
∵
ϕ
(
1
)
+
ϕ
(
2
)
+
ϕ
(
5
)
+
ϕ
(
10
)
=
10
∴
ϕ
(
10
)
=
10
−
ϕ
(
1
)
−
ϕ
(
2
)
−
ϕ
(
5
)
\because \phi(1)+\phi(2)+\phi(5)+\phi(10)=10\\ \therefore \phi(10)=10-\phi(1)-\phi(2)-\phi(5)\\
∵ϕ(1)+ϕ(2)+ϕ(5)+ϕ(10)=10∴ϕ(10)=10−ϕ(1)−ϕ(2)−ϕ(5)
So it is to find all the factors. At this time, an algorithm similar to the Elatoseni screening method needs to be used. The essence of the Toseni filtering algorithm is that we should not look for all factors in front. Instead, I go to the back to find all the multiples to subtract myself, which is slightly different from the forward traversal algorithm of regular arrays. I'll use φ(10) as an example to explain it
The first step is initialized to n
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| φ(x) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
All the numbers after 1 are multiples of 1, so all φ(1) is subtracted, so it becomes:
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| φ(x) | 0 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
All the multiples of 2 after 2 are subtracted by φ(2), so they become:
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| φ(x) | 0 | 1 | 1 | 2 | 2 | 4 | 4 | 6 | 6 | 8 | 8 |
All multiples of 3 after 3 are subtracted by φ(3), so it becomes:
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| φ(x) | 0 | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 6 | 6 | 8 |
4. All the multiples of 4 after 4 are subtracted by φ(4), so it becomes:
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| φ(x) | 0 | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 8 |
All multiples of 5 after 5 are subtracted by φ(5), so it becomes:
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| φ(x) | 0 | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 |
Then after understanding the algorithm, the code becomes easier:
# _*_ coding:utf-8 _*_
def euler_totient(n):
phi = [i for i in range(0, n + 1)]
for i in range(1, n + 1):
# Subtract all the following i from phi[i]
for j in range(i << 1, n + 1, i):
phi[j] -= phi[i]
return phi[n]
if __name__ == '__main__':
print(euler_totient(10))
Test results:
4