To find prime factors of a given number, why set the second statement of the for loop to i * i <= userInput instead of i <= userInput?

Question

I'm new to Java and am trying to solve the problem of finding all prime factors of a given number. I have been told if I set the second statement of the for loop to i * i <= userInput instead of i <= userInput, the program will be much more efficient.

I can't get my head around as to why this is the case. What is the reason behind it?

Scanner sc = new Scanner(System.in);
int userInput = sc.nextInt();
        sc.close();
        System.out.println("Prime factors of " + userInput + " include: ");

        for (int i = 2; i * i <= userInput; i++){
            while(userInput % i == 0){
                System.out.print(i + " ");
                userInput /= i;
            }
        }
        if (userInput > 1){
            System.out.print(userInput);
        } else {
            System.out.print("");
        }

score 2 · Accepted Answer · answered Jan 18 '16 at 12:03

In fact this code will find not only prime factors - it will search for all factors. If your number is Y can be represented as X * X, any factor below X will have matching factor greater than X. So you need only to check half of all cases. For 14 when you found that 2 is factor, matching factor is 7, so you don't need to check matching factor of 7. Thats why your condition is contain i*i.

score 2 · Answer 2 · answered Jan 18 '16 at 12:09

2

Because it cuts the search space from N to the square root of N.

answered Jan 18 '16 at 12:09

user207421

305,947
44
307
483

score 0 · Answer 3 · answered May 03 '21 at 08:27

You could write as:

for (int i = 2; i <= Math.sqrt(userInput); i++)

This reduces the number of iterations of the loop from N to square root of N. Eg: if N = 16, then the iterations would be reduced to 4. For a smaller N, this does not seem much but you will see the difference as N increases in value.

Imagine N=16, the factors are: 


1,16 --   you are disallowing this anyway but I present if for completeness
2,8
4,4
------ The ones below are already covered and do not need to be looped through --------
8,2
16,1

A faster way to do that would be to find an incrementer and that is linked here.

To find prime factors of a given number, why set the second statement of the for loop to i * i <= userInput instead of i <= userInput?

3 Answers3