Least integer divisor without square root calculation

Question

This code gives the smallest integer divisor. But the problem is that I have to calculate the square root. Is there a way so that I cannot explicitly calculate the square root?

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"); } 

Answer 1

Since code-efficiency was one of the tags, modify the answers a bit:

 while ((n%d) && (d<n/d)) d+=2; 

The compiler is more likely to reuse the result of the division operator in this way.

Considering the compiler output for gcc -O3 in the version of the loop that I propose, there is only one separation 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 version while ((n%d) && d*d < n) d+=2; 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 that it performs both multiplication and division by each iteration.

Answer 2

Sure. Instead of this:

 while((n%d!=0)&&d<r) 

You can write

 while((n%d!=0) && d*d < n) 

Answer 3

Instead of checking if d < sqrt(n) , you can check if d*d < n like this:

 while((n%d!=0)&&d<r) 

it should be

 while((n%d!=0) && d*d < n) 

Answer 4

This algorithm uses the square root to reduce the number of iterations in the loop. Significantly reduced. I don’t know what problem you have with the square root, but you can calculate the square root with approximately 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 performance loss)