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

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

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 * dr改为此行中的while((n%d!=0)&&d或只是将r改为n (但性能下降)