파이의 합 - PHISUM

문제 링크(koitp.org/problem/PHISUM/)

에라토스테네스의 체를 이용해서 특정 수의 소인수 하나(p)를 저장해둔다.

∅(x)를 계산할 때에는 다음과 같은 2가지 경우가 있다.

1. x가 소수인 경우

∅(x) = x-1

2. x가 소수가 아닌 경우

∅(x) = ∅(n)∅(m) ( gcd(n, m) = 1, n=p^q )

∅(n) = (p-1)[p^(q-1)]