시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 3850 | 721 | 610 | 27.515% |
양의 정수 n이 주어졌을 때, n보다 작은 양의 정수 중에서 n과 서로소인 수 개수를 구하는 프로그램을 작성하시오.
두 정수 a와 b가 서로소가 되려면 x > 1, y > 0, z > 0이면서, a = xy, b= xz를 만족하는 정수가 없어야 한다.
입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 n ≤ 1,000,000,000으로 이루어져 있다.
입력의 마지막 줄에는 0이 주어진다.
입력으로 주어진 n마다 n보다 작으면서 서로소인 양의 정수의 수를 출력한다.
7 12 0
6 4
Contest > Waterloo's local Programming Contests > 1 June, 2002 E번