計算從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)<=n作爲你的for循環，那麼它的早期檢查的中間子句和你跳出循環越快的。
• 你不需要檢查，看看是否(i*i)%2==0，因爲'我'總是積極的，正方形總是正數。
• 考慮到這兩個變化，你可以去掉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任何奇i，i*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; 
}