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

}

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

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.