一个整数的最小除数不explcitly计算平方根 [英] smallest divisor of an integer without computing the square root explcitly

问题描述

这code给出一个整数的最小除数。但问题是，我要计算平方根。有没有办法让我没有明确计算平方根？

  INT D，R，N;
scanf函数（％d个，和放大器; N）;
如果（N％2 == 0）
{
    的printf（2 ANS）;
}
其他
{
    R =开方（N）;
    D = 3;
    而（（正％D = 0）及！和D＆所述; r）的
    {
        D = D + 2;
    }
    如果（N％D == 0）
        的printf（ANS为％d，D）;
    其他
        输出（ANS是1）;
}
 

解决方案

由于 code-效率是变量之一，调整提供了一个有点问题的答案：

 ，而（（N％D）及及（D＆LT; N / D））D + = 2;
 

编译器更可能重复使用除法运算的结果这样

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

  L18：
        CMPL％ESI，％ECX
        JLE L13
        MOVL％EBX，％eax中
        ADDL $ 2，％ESI
        cltd
        idivl％ESI
        为test1％EDX，EDX％
        MOVL％EAX，ECX％
        JNE L18
        .p2align 4日，15
L13：
 

虽然，在，而（（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
        为test1％EDX，EDX％
        JNE L8
        .p2align 4日，15
L3：
 

很显然它是既做乘法和除法每次迭代。

This code gives the smallest divisor of an integer. But the problem is I have to calculate the square root. Is there a way so that I don't have to calculate the square root explicitly?

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

解决方案

Since code-efficiency was one of the tags, tweak the answers provided a bit:

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

The compiler is more likely to reuse the result of the division operator this way.

Looking at the compiler output for gcc -O3 on the version of the loop I propose, there is only one division operation per iteration, and the result is used for both comparisons:

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, the while ((n%d) && d*d < n) d+=2; version gives:

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:

And it is clear it is doing both the multiplication and the division each iteration.

这篇关于一个整数的最小除数不explcitly计算平方根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！