math Prime checking


Example

Please note that by definition 1 is not a prime number. To check if a number n is a prime we should try to find a divisor i of n. If we cannot, then n is a prime. We have found a divisor when n % i == 0 evaluates to true. We only need to try odd numbers, since there's only one even prime, namely 2, which we'll treat as a special case. Additionally, only the numbers up to and including sqrt(n) are possible divisors, because when n = a * b then at least one of the factors is at most sqrt(n).

To check whether or not a number is a prime number the following algorithm can be used:

boolean isPrime (int n) {
    if (n < 2) {
        return false;
    }
    if (n % 2 == 0) {
        return n == 2;
    }
    for (int i = 3; i*i <= n; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true ;
}