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

本文介绍了一个整数的最小除数不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.