오일러 피(phi)함수를 거듭 연산했을 때 몇 번에 0이 되는가 ?

phi = [0]*1000010

for i in range(1000001):
    phi[i] = i
for i in range(2,1000001):
    if(phi[i] == i):
        for j in range(i,1000001,i):
            phi[j] = phi[j] * (i-1) // i
phi[1] = 0
def countphi(k,cnt):
    if(k==0):
        return cnt
    return countphi(phi[k],cnt+1)

lis =[]
for i in range(1001):
    lis.append(countphi(i,0))

print(max(lis))

대충 피함수 구하는 체(sieve) 랑 재귀돌려서 리스트에 넣었다.

 

1~1001 까지는 최대 11번이면 0에 도달하고

1~10001 까지는 최대 14번이면 0에 도달한다.

 

오일러 정리 쓸 때 유용하게 써먹을 수 있습니다