How to check if a number is prime

Short answer

A prime number is divisible only by 1 and itself. It is enough to try divisors up to the square root:

boolean isPrime(int n) {
    if (n < 2) {
        return false;
    }
    for (int i = 2; (long) i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}
 
void main() {
    IO.println(isPrime(17));
    IO.println(isPrime(21));
    IO.println(isPrime(1));
}

Output:

true
false
false

All primes up to N

Filter a range of numbers with the same check:

boolean isPrime(int n) {
    return n > 1 && IntStream.rangeClosed(2, (int) Math.sqrt(n)).noneMatch(i -> n % i == 0);
}
 
void main() {
    IO.println(IntStream.rangeClosed(1, 30).filter(this::isPrime).boxed().toList());
}

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Very large numbers

For huge numbers BigInteger has a probabilistic check — with a parameter of 20 a mistake is practically impossible:

void main() {
    var big = new BigInteger("170141183460469231731687303715884105727");
    IO.println(big.isProbablePrime(20));
}

Output:

true

Common mistake

Treating 1 as prime or trying divisors up to n. The first gives a wrong answer, the second makes the code slow. The condition i * i <= n can overflow in int for numbers near Integer.MAX_VALUE, so the first example multiplies in long.

Thanks for reading!

Short answer

All primes up to N

Very large numbers

Common mistake

Functions used in this recipe

Thanks for reading!