CODEWITHSUNDEEP
calgorithmperformance
jairaj
jairaj

Reputation: 1869

smallest divisor of an integer without computing the square root explcitly

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

Upvotes: 3

Views: 10932

Answers (4)

jxh
jxh

Reputation: 70472

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.

Upvotes: 7

mishadoff
mishadoff

Reputation: 10789

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)

Upvotes: 1

flight
flight

Reputation: 7272

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)

Upvotes: 3

Donotalo
Donotalo

Reputation: 13025

Sure. Instead of this:

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

you can write

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

Upvotes: 5

Related Questions