Checking for Primality

A prime number has exactly two factors: 1 and itself.

Brute force: loop from 1 to n, count how many values evenly divide n, and check if that count equals 2.

static boolean checkPrime(int n){
    int count = 0;
    for (int i = 1; i <= n; i++){
        if (n % i == 0){
            count ++;
        }
    }
    return count == 2;
}

This is inefficient for large numbers. The key optimization: factors come in pairs — if a is a factor of n, then n/a is also a factor. The factors of n are symmetric around sqrt(n), so you only need to check up to sqrt(n) and pick up each factor’s pair automatically.

For example, if n = 36, checking up to sqrt(36) = 6 finds 1, 2, 3, 4, 6. Each of those gives you a paired factor — 36/1, 36/2, 36/3, 36/4, 36/6 = 36, 18, 12, 9, 6 — so you get all the factors without checking past 6.

static boolean checkPrime(int n){
    int count = 0;
    for (int i = 1; i <= n; i++){
        if (n % i == 0){
            count++;
            if((n/i) != i) count++;
        }
    }
    if(count == 2){
        return true;
    } else{
        return false;
    }
}