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

猛烈な速さ。各平方を計算するには、足し算を 2 回行うだけです。

Answer 2

私はあなたのソリューションが好きです。私が行う唯一の提案は次のとおりです。

• as を for ループの中間句に置くと、(i*i)<=n以前にチェックされ、ループから抜け出すのが早くなります。
• (i*i)%2==0'i' は常に正であり、正の 2 乗は常に正であるため、if を確認する必要はありません。
• これら 2 つの変更を念頭に置いて、for ループ内の if ステートメントを削除し、単に出力することができます。

Answer 3

偶数の二乗は偶数です。したがって、もう一度確認する必要はありません。以下はコードです。

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

Answer 4

ループ内の の最大値はiの平方根の下限になるはずですn。

その理由は、iこれよりも大きい (整数)の 2 乗は よりも大きくなるためnです。したがって、この変更を行う場合は、それを確認する必要はありませんi*i <= n。

また、他の人が指摘しているように、すべての偶数の2乗が偶数であるため、i*i偶数であることを確認しても意味がありません。

そして、奇数は奇数であるため、奇数を 無視するのは正しいことです。iii*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;
}