문제
Farey 수열 Fn은 정수 n (n≥2) 이 있을 때 기약분수 a/b (0＜a＜b≤n 그리고 gcd(a,b)=1)들의 집합을 뜻한다. 몇 개를 나열해보면 다음과 같다.
F2 = {1/2} F3 = {1/3, 1/2, 2/3} F4 = {1/4, 1/3, 1/2, 2/3, 3/4} F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
Fn에 포함된 원소의 개수를 하라.
제출파일은 farey.cpp로 하고 실행시간은 1초를 넘을 수 없다.
입력
입력파일은 INPUT.TXT로 한다. N이 계속 들어오다가 0이 입력되면 끝난다. N은 10^6이하의 정수이다.
출력
출력파일은 OUTPUT.TXT로 한다. 입력에 대해 Fn에 속하는 숫자의 개수를 출력한다.
예제
2
3
4
5
0
1
3
5
9
로그인해야 코드를 작성할 수 있어요.