整数的最小除数,而不是计算平方根
此代码给出整数的最小除数。 但问题是我必须计算平方根。 有没有办法让我不必明确计算平方根?
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"); }
由于code-efficiency
是标签之一,请稍微调整一下答案:
while ((n%d) && (d
编译器更有可能以这种方式重用除法运算符的结果。
在我提出的循环版本上查看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:
很明显,它每次迭代都在进行乘法和除法。
当然。 而不是这个:
while((n%d!=0)&&d
你可以写
while((n%d!=0) && d*d < n)
而不是检查是否d < sqrt(n)
,您可以检查是否d*d < n
所以:
while((n%d!=0)&&d
应该
while((n%d!=0) && d*d < n)
该算法使用平方根来减少循环中的迭代次数。 大大减少。 我不知道你用平方根有什么问题,但是你可以用这些算法近似计算平方根,或者只需将d
改为d * d
, r
改为此行中的while((n%d!=0)&&d
r
改为n
(但性能下降)