一个整数的最小除数,而不是explcitly计算平方根

Question

此代码给出整数的最小除数.但问题是我必须计算平方根.有没有办法让我不必明确计算平方根？

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");
}

Answer 1

既然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:

很明显,它每次迭代都在进行乘法和除法.

Answer 2

当然.而不是这个:

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

你可以写

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