時間制限:1000ミリ秒
メモリ制限:65536KB
問題
正の整数nが与えられたとき、nより小さい正の整数で、nと互いに素なものの数を求めるプログラムを作成せよ。2つの正の整数a,bが互いに素であるというのは、x > 1, y > 0, z > 0であって、 a = xy, b = xzを満たす正の整数x,y,zが存在しないことをいう。
入力
入力はいくつかのテストケースを含む。各テストケースは1行で、各行は正の整数n(n <= 1,000,000,000)を含む。0のみを含む行は、テストケースの終わりである。
出力
各テストケースに対して、nより小さい正の整数で、nと互いに素なものの数を含む1行を出力せよ。
入力の例
7 12 0
出力の例
6 4
出典
Waterloo local 2002.07.01