서로소 > 문제은행

fff

1166 : 서로소

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
63 회   
시도횟수
458 회   

문제

입력된 정수 n에 대해 서로소인 1 이상 n이하의 정수의 갯수를 출력하는 프로그램을 작성하라.
여기서 임의의 정수 n의 서로소란, n과의 공약수가 1밖에 없는 숫자를 뜻한다.


입력형식

입력은 테스트 케이스 여러개로 이루어진다. 테스트 케이스는 한 줄로 이루어지며, 각 줄에는 정수 n(n≤1,000,000,000)이 입력된다. 입력의 마지막에는 0 이 입력되며, 이는 처리하지 않고 프로그램을 종료한다.


출력형식

각 테스트 케이스에 대한 서로소의 개수를 한줄에 하나씩 출력한다.


입력 예

7
12
0

출력 예

6
4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP