smallest divisor of an integer without computing the square root explcitly
Solution 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.
Solution 2
Sure. Instead of this:
while((n%d!=0)&&d<r)
you can write
while((n%d!=0) && d*d < n)
Solution 3
Instead of checking if d < sqrt(n)
, you can check if d*d < n
so:
while((n%d!=0)&&d<r)
should be
while((n%d!=0) && d*d < n)
Solution 4
This algorithm uses square root to reduce number of iteration in cycle. Greatly reduce. I don't know what problem you have with square root, but you can calculate square root approximately with these algorithms or just change d
to d * d
, r
to n
in this line while((n%d!=0)&&d<r)
or just change r
to n
(but with losing performance)
Comments
-
jairaj almost 2 years
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"); }