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

由于code-efficiency是标签之一，因此请稍微调整一下提供的答案：

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

编译器更有可能以这种方式重用除法运算符的结果。

查看gcc -O3我建议的循环版本的编译器输出，每次迭代只有一个除法运算，结果用于两个比较：

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)您可以检查是否是这样，而不是检查if 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 * d或更改为（但性能下降）rnwhile((n%d!=0)&&d<r)rn

于 2012-07-28T09:01:45.643 回答