这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< 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.