레야몬

1. 문제를 읽고 이해한다. 자연수 n \(1\leq n\leq 10^{12}\) GCD(n, k) = 1을 만족하는 자연수 $$ 1 \leq k \leq n $$ 의 개수 출력 2. 문제를 익숙한 용어로 재정의한다. n과 서로소인 수의 개수 출력(1도 포함) 3. 어떻게 해결할지 계획을 세운다. 에라토스테네스의 체로 소수를 구하기( $$ \sqrt{n} $$ 가지) O( $$ \sqrt{n} $$ ) 오일러 피 하수(Euler phi function)을 사용하기 4. 계획을 검증한다. O( $$ \sqrt{n} $$ ) = $$ \10^{6} $$ = 1, 000, 000 5. 프로그램으로 구현한다. 6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다. n과 서로소가 아니라 n의 소인수를 구..