Algorithms to find prime factors

Question

I found an algorithm written in C that solves the prime factor problem, but I don't understand why we have i < sqrt(n), can anybody show me why ?

// Program to print all prime factors 
# 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) // I don't get why i <= sqrt(n) here !??
    { 
        // 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) 
        printf ("%d ", n); 
}

If you have checked all factors of `n` smaller than or equal to `sqrt(n)`, what does that tell you about the higher factors (or vice versa)? If `p * q = n`, and `p > sqrt(n)`, what do you know about `q`? — EOF, Apr 16 '20 at 08:19
Thanks, I get it now that n will have at least a prime factor smaller than sqrt(n) and a prime factor that is larger than sqrt(n), otherwise n is a prime number. — Thang, Apr 16 '20 at 09:00
@Thang No, there is no guarantee that a composite number will have a prime factor larger than `sqrt(n)`. Consider `16 == 2 * 2 * 2 * 2`, which has only prime factors less than `sqrt(16) == 4`. — EOF, Apr 16 '20 at 10:04
`sqrt(n)` in C/C++ can get inprecise for large numbers, consider using `i*i <=n` instead — Photon, Apr 16 '20 at 13:40
@Photon for large numbers `i*i` can get you an integer overflow, consider using `i <= n / i` instead. correctness first, efficiency later. — Will Ness, Apr 16 '20 at 15:21
@Thang "smaller than" ***or equal to*** " sqrt(n)". and your comment is correct if you strike out "prime" in "and a prime factor that is larger than sqrt(n)". ", otherwise n is a prime number" precisely, and that's the reason for the last check `(n > 2)`, it will be true if we've stopped at the sqrt i.e. if the (last) `n` was prime. — Will Ness, Apr 16 '20 at 15:23

Syed Waris · Answer 1 · 2020-04-16T14:27:05.910

why we have i < sqrt(n),

Suppose you need to find factors of 9. Write it as follows:

1 * 9  = 9
3 * 3  = 9

// 9 * 1 = 9 but it is the same case as first

From above you can see as soon as you get till the row where is is 3 * 3 you dont need to explore further. And note that this 3 is the square root of 9. For 9, factors are 1,3,9.

Next example 36:

1 * 36 = 36
2 * 18 = 36
3 * 12 = 36
4 * 9 = 36
6 * 6 = 36
// No need to go further as the digits will repeat

Again you see after the square root 6, we dont need to explore further as it will not give us NEW digits as factors. From above, factors of 6 : 1,2,3,4,6,9,12,18,36. And prime factors are 2,3.

In above 2 examples I took perfect squares as examples. Lets take a different example which is not a perfect square, 24 for example: Square root of 24 is 4 point something. So we will see that we will have to stop at 4.

1 * 24 = 24
2 * 12 = 24
3 * 8  = 24
4 * 6  = 24

// Stop not process further
// Even if proceeded the next line would be 6 * 4 = 24 but we have already obtained these numbers.

Therefore we stop at sqrt(24).

To Conclude: For 'n', if we are unable to find a prime number before sqrt(n), then it is guaranteed, numbers above sqrt(n) will not contain any prime numbers for n.

(edited) it is much better to use primes as examples here. that's the case where the gains are. and what you show for 24 is not how the algorithm works. it divides the smaller factors out, so it goes n=24: {print 2; n=12}, {print 2; n=6}, {print 2, n=3}, LOOP, i = 3, (i <= **sqrt(3)**) IS FALSE, STOP_LOOP, 3 > 2 IS TRUE, {print 3}. — Will Ness, Apr 16 '20 at 15:28
Ok Thanks, I have explained the concept behind code. If I would have chosen a perfect prime number as example then the logic might not come out clearly. After seeing the examples on 9, 36 and 24, the OP can immediately think of how the logic can be applied on a prime number or in fact ANY number. — Syed Waris, Apr 16 '20 at 15:31
no. it only applies to prime numbers. re-read my comment. cheers, :) — Will Ness, Apr 16 '20 at 15:40

Algorithms to find prime factors

1 Answers1