c - 计算从 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

让我不仅说明快速解决方案，还说明如何推导它。从列出所有方 block 的快速方法开始，然后从那里开始工作(伪代码):

max = n*n
i = 1
d = 3

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

所以，从 4 开始，只列出偶数方 block :

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

快如闪电。计算每个平方只需要两次加法。