'Why do you divide by two when checking prime numbers in Java?

I was looking over this on YouTube and saw some code. I got most of it but didn't understand at all the reason why you the value n divide by two. Could someone please explain it?

import java.util.ArrayList;

public class Primes {

    public static void main(String[] args) {
        
        System.out.println(findPrimes(1, 100));
        
    }
    
    public static ArrayList<Integer> findPrimes(int start, int end) {
        
        ArrayList<Integer> primes = new ArrayList<Integer>();
        
        for(int n = start; n < end; n++) {
            boolean prime = true;
            
            int i = 2; 
            while(i <= n/2) {
                if(n % i == 0) {
                    prime = false;
                    break;
                }
                i++;
            }
            
            if(prime) {
                primes.add(n);
            }
        }
        
        return primes;
    }

}
java


Solution 1:[1]

A number can only be divided by a number that is less than or equal to its half. Or the number to be divided itself.

Solution 2:[2]

Here, we are checking till n/2 so that the number of iterations and the load on the system reduces and make the program more efficient. Since the greatest factor which can divide a number (excluding itself) is half of the number, we check only till that point. There is no point of checking beyond that.

Solution 3:[3]

It's an attempt to improve the efficiency of the solution by stopping the loop at a point where the algorithm will no longer find any more prime factors.

However, it's suboptimal. If n == a * b and a <= b, a can be no higher than the square root of n. Therefore, checking for i <= Math.sqrt(n) would eliminate many more unnecessary iterations of the loop for large values of n.

A further improvement could be made by iterating over known values of primes instead of incremental values of i, since once you've established that a number isn't divisible by 3 there's no point checking 6, 9, 12 and so on.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 KP Singh
Solution 2 Utkarsh Sahu
Solution 3

Related Questions