欧拉筛+欧拉函数
在欧拉筛法执行的过程当中,可以间接求得每个数的欧拉函数。对于不同的数,可以分三种情况讨论:
(1)质数:对于质数$N$,与$1~N$中互质的总数显然是$N-1$,因此$$\phi (N) = N - 1$$
(2)第一类合数:假设一个合数$C$,它是一个质数$P$和以这个质数为最小质因子的数$N$的积,即$N\ mod\ P = 0$,$C = N×P$,那么根据欧拉函数定义,$$\phi (C) = \phi (NP) = \phi (N) × P$$
(3)第二类合数:假设一个合数$C$,它是一个质数$P$和与这个质数互质的数$N$的积,即$N\ mod\ P \neq 0$, $C = N×P$,因此根据欧拉函数定义:$$\phi (C) = \phi (NP) = \phi (N) × (P-1)$$
综上,可以得出
代码
时间复杂度:$O(n)$
def get_Eulers(n):
phi = [0 for _ in range(n+1)]
phi[1] = 1
primes = []
is_prime = [1 for _ in range(n+1)]
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
phi[i] = i - 1
j = 0
while primes[j]*i <= n:
is_prime[primes[j]*i] = 0
if i % primes[j] == 0:
phi[primes[j]*i] = phi[i]*primes[j]
break
phi[primes[j]*i] = phi[i]*(primes[j]-1)
j += 1
return sum(phi)
n = int(input())
print(get_Eulers(n))
参考资料
[1] https://www.acwing.com/video/28/
[2] 欧拉筛:https://www.acwing.com/file_system/file/content/whole/index/content/5511889/
[3] 欧拉函数:https://www.acwing.com/file_system/file/content/whole/index/content/5539443/