AcWing 874. 筛法求欧拉函数（欧拉函数）

题目链接
https://www.acwing.com/problem/content/876/
思路
对于一个数x如果是质数，那么它的欧拉函数就为

x

−

1

x-1

x−1，对于其他合数我们可以将其拆成最小的质数的积，那么这个过程我们就可以通过欧拉筛法来计算欧拉函数值，现在我们还有两种情况需要讨论
如果i能整除prime[j]说明prime[j]是i的一个质因子，那么对于i*prime[j]来说其实就是

p

h

AcWing 874. 筛法求欧拉函数（欧拉函数）最先出现在Python成神之路。