프로그램 명: relatives
제한시간: 1 초
양의 정수 n 이 주어질 때 n 보다 작은 양의 정수 중에서 n 과 서로 소(relatively prime)인 수의 개수를 구하는 문제이다.
- 서로 소란?
-
두 정수 a , b 가 서로 소 이면 x >1 , y>0 , z>0 인 a=xy , b=xz 가 존재하지 않는다.
입력
여러개의 테스트 데이터가 입력으로 주어진다 . n 의 범위는 n <= 1,000,000,000
입력의 끝은 0 이다.
출력
출력 예의 형식으로 개수를 출력한다.
입출력 예
입력
7
12
0
출력
6
4
출처: Waterloo local 2002.07.01
[질/답]
[제출 현황]
[푼 후(0)]