有没有办法在不改变逻辑和语言的情况下优化以下代码？原因：UVa 超出时间限制

Question

问题是UVa 10110

#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;
}

这在 C 中可能吗？ 不允许使用任何其他语言:( 他们使用的语言：ANSI C 5.3.0 - GNU C 编译器，带有选项：-lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE 运行时间不应超过3秒。

Answer 1

循环到

n/2

是非常慢，因为代码只需要循环到

sqrt(n)

。

    a=n/2;
    d=0;
    for (i=1; i<=a; i++) {
        if (n%i==0) {
          d++;
        }
    }

可替换为

    d=0;
    if (n > 1) { 
      d += 1;
    }
    for (i=2; i < n/i; i++) {
        if (n%i==0) {
          d += 2;
        }
    }
    for (; i == n/i; i++) {
        if (n%i==0) {
          d += 1;
        }
    }

并且由于后面的代码只需要

d

的均匀性，因此

for (i=1; i < a/i; i++) {

循环除了使

i

达到接近

n

的平方根之外几乎没有其他作用。考虑测试

n

是否是完美正方形，并在

n <= 1

时注意边缘情况。

请勿使用

...; i*i < n; i++

，因为当

i*i

是

n

附近的较大值时，

UINT_MAX

可能会溢出。