Prime factors in C

Question

I came across this effective program for printing all the prime factors of a given number:

# include <stdio.h>
# include <math.h>

// A function to print all prime factors of a given number n
void primeFactors(int n)
{
    // Print the number of 2s that divide n
    while (n%2 == 0)
    {
        printf("%d ", 2);
        n = n/2;
    }

    // n must be odd at this point.  So we can skip 
    // one element (Note i = i +2)
    for (int i = 3; i <= sqrt(n); i = i+2)
    {
        // While i divides n, print i and divide n
        while (n%i == 0)
        {
            printf("%d ", i);
            n = n/i;
        }
    }

    // This condition is to handle the case when n 
    // is a prime number greater than 2
    if (n > 2&&n%2!=0)
        printf ("%d ", n);
}

/* Driver program to test above function */
int main()
{
    int n = 315;
    primeFactors(n);
    return 0;
}

The output is 3 3 5 7. That's perfect.

But I have a confusion in this algorithm. The sqrt() returns a float value. If it is displayed in integer format in printf, it returns some random, large number. If this is the case, the condition in the for loop should fail, because sqrt() as an integer returns a random number. Could someone explain this?

Plus,could someone verify this? This algorithm was wrongly written in geeksforgeeks website as if(n>2) instead of if(n>2&&n!=0), which was added by me. Someone please verify this algorithm. Thanks in advance.

Answer 1

If you try to print the value of sqrt(n) as if it were an integer:

printf("sqrt(n) = %d\n", sqrt(n)); // Don't do this

then you have undefined behavior. sqrt() returns a result of type double. The compiler doesn't know (or isn't required to know) the expected type of the argument. It's up to you to pass an argument of the correct type. The above call to printf has undefined behavior.

In other contexts, where the type and expected type of an expression are unambiguous, the language requires implicit conversions. In particular, in the expression i <= sqrt(n), where i and n are of type int, the argument n is converted from int to double (the parameter type for sqrt()), and the value ofiis also converted frominttodouble`. The result is likely to be what you expected it to be.

Incidentally, this:

for (int i = 3; i <= sqrt(n); i = i+2) ...

is likely to be inefficient. The sqrt function is relatively expensive, and it's going to be called on each iteration of the loop. (Precomputing sqrt(n) is a good solution in some cases, but here the value of n can change within the loop.)

An alternative is:

for (int i = 3; i*i <= n; i += 2) ...

which avoids the complications of floating-point arithmetic (but think about whether i*i can overflow).

(It would be nice if C had an integer square root function in the standard library, but it doesn't.)