计算从1到n的所有偶数平方的最快方法？

Question

我在c中这样做了:

#include<stdio.h>

int main (void)
{
 int n,i;

 scanf("%d", &n);

 for(i=2;i<=n;i=i+2)
 {
   if((i*i)%2==0 && (i*i)<= n)
      printf("%d \n",(i*i));
 }
 return 0;
}

什么是更好/更快的方法来解决这个问题？

Answer 1

让我说明一个快速的解决方案,以及如何推导它.从快速列出所有正方形并从那里开始工作(伪代码)开始:

max = n*n
i = 1
d = 3

while i < max:
    print i
    i += d
    d += 2

所以,从4开始并仅列出偶数正方形:

max = n*n
i = 4
d = 5

while i < max:
    print i
    i += d
    d += 2
    i += d
    d += 2

现在我们可以在while循环结束时缩短那个混乱:

max = n*n
i = 4
d = 5

while i < max:
    print i
    i += 2 + 2*d
    d += 4

请注意,我们一直在使用2*d,所以最好继续计算:

max = n*n
i = 4
d = 10

while i < max:
    print i
    i += 2 + d
    d += 8

现在注意我们不断添加2 + d,所以我们可以通过将其合并到d以下内容中做得更好:

max = n*n
i = 4
d = 12

while i < max:
    print i
    i += d
    d += 8

快速燃烧.计算每个方块只需要两次加法.