시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 215 96 81 46.023%

문제

양의 정수 n이 주어졌을 때, n보다 작은 양의 정수 중에서 n과 서로소인 수 개수를 구하는 프로그램을 작성하시오.

두 정수 a와 b가 서로소가 되려면 x > 1, y > 0, z > 0이면서, a = xy, b= xz를 만족하는 정수가 없어야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 n ≤ 1,000,000,000으로 이루어져 있다.

입력의 마지막 줄에는 0이 주어진다.

출력

입력으로 주어진 n마다 n보다 작으면서 서로소인 양의 정수의 수를 출력한다.

예제 입력 1

7
12
0

예제 출력 1

6
4
W3sicHJvYmxlbV9pZCI6IjQzNTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMWNcdWI4NWNcdWMxOGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBuXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBuXHVhY2ZjIFx1YzExY1x1Yjg1Y1x1YzE4Y1x1Yzc3OCBcdWMyMTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjODE1XHVjMjE4IGFcdWM2NDAgYlx1YWMwMCBcdWMxMWNcdWI4NWNcdWMxOGNcdWFjMDAgXHViNDE4XHViODI0XHViYTc0IHggJmd0OyAxLCB5ICZndDsgMCwgeiAmZ3Q7IDBcdWM3NzRcdWJhNzRcdWMxMWMsIGEgPSB4eSwgYj0geHpcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM1YzZcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBuICZsZTsgMSwwMDAsMDAwLDAwMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IG5cdWI5YzhcdWIyZTQgblx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3M2NcdWJhNzRcdWMxMWMgXHVjMTFjXHViODVjXHVjMThjXHVjNzc4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MzU1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmVsYXRpdmVzIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBuLCBhIHBvc2l0aXZlIGludGVnZXIsIGhvdyBtYW55IHBvc2l0aXZlIGludGVnZXJzIGxlc3MgdGhhbiBuIGFyZSByZWxhdGl2ZWx5IHByaW1lIHRvIG4/IFR3byBpbnRlZ2VycyBhIGFuZCBiIGFyZSByZWxhdGl2ZWx5IHByaW1lIGlmIHRoZXJlIGFyZSBubyBpbnRlZ2VycyB4ICZndDsgMSwgeSAmZ3Q7IDAsIHogJmd0OyAwIHN1Y2ggdGhhdCBhID0geHkgYW5kIGIgPSB4ei48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIGFyZSBzZXZlcmFsIHRlc3QgY2FzZXMuIEZvciBlYWNoIHRlc3QgY2FzZSwgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgYSBsaW5lIHdpdGggbiAmbHQ7PSAxLDAwMCwwMDAsMDAwLiBBIGxpbmUgY29udGFpbmluZyAwIGZvbGxvd3MgdGhlIGxhc3QgY2FzZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgdGhlcmUgc2hvdWxkIGJlIHNpbmdsZSBsaW5lIG9mIG91dHB1dCBhbnN3ZXJpbmcgdGhlIHF1ZXN0aW9uIHBvc2VkIGFib3ZlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Waterloo's local Programming Contests > 1 June, 2002 E번