#include <stdio.h>
int main()
{
unsigned int n,a,d,i,j;
while (1)
{
scanf("%u",&n);
if (n==0)
{
break;
}
a=n/2;
d=0;
for (i=1; i<=a; i++)
{
if (n%i==0)
{
d++;
}
}
if (d%2==0)
{
printf("yes\n");
}
else
{
printf("no\n");
}
}
return 0;
}
字符串
不允许使用任何其他语言:(他们使用的语言:ANSI C 5.3.0 - GNU C编译器,带有选项:-lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE运行时间不应超过3秒。
1条答案
按热度按时间zzlelutf1#
循环到
n/2
非常慢,因为代码只需要循环到sqrt(n)
。字符串
可替换为下面的,循环次数最多为
sqrt(n)
。型
由于后面的代码只需要
d
的均匀性,for (i=1; i < a/i; i++) {
循环除了使i
接近n
的平方根之外没有什么作用。考虑测试n
是否是完美的平方,并注意n <= 1
的边缘情况。(小心double sqrt(double)
,因为这会导致意外的舍入。)注意:不要使用
...; i*i < n; i++
,因为当n
是UINT_MAX
附近的大值时,i*i
可能会溢出。学究式地,使用一个更宽的类型
unsigned
,它可能比需要的范围小。建议使用unsigned long
。