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

让我不仅说明一个快速解决方案，还说明如何推导出它。从列出所有方块的快速方法开始，然后从那里开始工作（伪代码）：

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

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

Answer 2

我喜欢你的解决方案。我会提出的唯一建议是：

• 将(i*i)<=nfor 放在 for 循环的中间子句，然后它会被更早地检查，并且你会更快地跳出循环。
• 您无需检查是否(i*i)%2==0，因为 'i' 始终为正数，而正平方始终为正数。
• 考虑到这两个变化，您可以摆脱 for 循环中的 if 语句并直接打印。

Answer 3

偶数的平方是偶数。所以，你真的不需要再次检查它。以下是代码，我建议：

for (i = 2; i*i <= n; i+=2)
     printf ("%d\t", i*i);

Answer 4

循环中的最大值i应该是 的平方根的底n。

原因是任何i大于此的（整数）的平方都将大于n。因此，如果您进行此更改，则无需检查i*i <= n.

此外，正如其他人所指出的那样，检查偶数i*i是没有意义的，因为所有偶数的平方都是偶数。

你忽略奇数 是对的，i因为任何奇数都是奇数。ii*i

具有上述更改的代码如下：

#include "stdio.h"
#include "math.h"

int main () 
{
    int n,i;

    scanf("%d", &n);

    for( i = 2; i <= (int)floor(sqrt(n)); i = i+2 ) {       
        printf("%d \n",(i*i));
    }

    return 0;
}