레야몬

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