源码:#include "stdio.h"
int main()
{
int n,i = 0;
scanf("%d",&n);
while(n)
{
int j,a = 1;
int t = n;
for(j = 2;j < n;j++)
if(t % j == 0)
{
t= t / j;
a= a * (j - 1);
}
if(a == 1)
a = t - 1;
else
a =a * t;
printf("%d\n",a);
scanf("%d",&n);
}
return 0;
}
原题:
LK的数学题
时间限制:1000 ms | 内存限制:65535 KB
难度:3
描述
LK最近遇到一个问题,需要你帮她一下。一个整数n,求[1,n)中,和n互素的数的个数。
输入
多组测试数据,每一行有一个整数n(n<1000000001),0表示输入结束。
输出
小于n同时和n互素的整数的个数
样例输入
7
12
0
样例输出
6
4