3

このコードは整数の最小の約数を与えます。しかし、問題は平方根を計算する必要があることです。平方根を明示的に計算する必要がないようにする方法はありますか？

int d,r,n;
scanf("%d",&n);
if(n%2==0)
{
    printf("2 is ans"); 
}
else
{
    r=sqrt(n);
    d=3;
    while((n%d!=0)&&d<r)
    {
        d=d+2; 
    }
    if(n%d==0)
        printf("ans is %d",d);
    else
        printf("ans is 1");
}
4

4 に答える 4

7

はタグの1つだったのでcode-efficiency、提供された回答を少し調整します。

while ((n%d) && (d<n/d)) d+=2;

コンパイラは、除算演算子の結果をこのように再利用する可能性が高くなります。

私が提案するループのバージョンでのコンパイラ出力を見ると、gcc -O3反復ごとに1つの除算演算しかなく、その結果が両方の比較に使用されます。

L18:
        cmpl    %esi, %ecx
        jle     L13
        movl    %ebx, %eax
        addl    $2, %esi
        cltd
        idivl   %esi
        testl   %edx, %edx
        movl    %eax, %ecx
        jne     L18
        .p2align 4,,15
L13:

一方、while ((n%d) && d*d < n) d+=2;バージョンは次のようになります。

L8:
        movl    %ecx, %eax
        imull   %ecx, %eax
        cmpl    %ebx, %eax
        jge     L3
        movl    %ebx, %eax
        addl    $2, %ecx
        cltd
        idivl   %ecx
        testl   %edx, %edx
        jne     L8
        .p2align 4,,15
L3:

そして、それが各反復で乗算と除算の両方を行っていることは明らかです。

于 2012-07-28T09:12:12.327 に答える
5

もちろん。これの代わりに：

while((n%d!=0)&&d<r)

あなたは書ける

while((n%d!=0) && d*d < n)
于 2012-07-28T08:59:57.333 に答える
3

かどうかを確認する代わりに、次のd < sqrt(n)ことを確認できますd*d < n。

while((n%d!=0)&&d<r)

する必要があります

while((n%d!=0) && d*d < n)
于 2012-07-28T09:00:16.753 に答える
1

このアルゴリズムは平方根を使用して、サイクルの反復回数を減らします。大幅に削減します。平方根でどのような問題があるのか​​わかりませんが、これらのアルゴリズムを使用して平方根を概算するか、この行でに変更するか、に変更dすることができます（ただし、パフォーマンスが低下します）d * drnwhile((n%d!=0)&&d<r)rn

于 2012-07-28T09:01:45.643 に答える