Проверка простого числа

25. Проверить число на простоту

Условие задачи:
Необходимо написать консольное приложение, которое считывает целое число и определяет, является ли оно простым.

Простое число — это натуральное число больше 1, которое делится без остатка только на 1 и на само себя.

Код:

public class PrimeChecker {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int number = scanner.nextInt();

        if (isPrime(number)) {
            System.out.println(number + " — простое число.");
        } else {
            System.out.println(number + " — не является простым.");
        }

        scanner.close();
    }

    public static boolean isPrime(int n) {
        // ваш код
    }
}

Примеры:

2  → простое число
4  → не является простым
17 → простое число

Спойлеры к решению

Подсказки

💡 Все числа n <= 1 не являются простыми.
💡 2 — единственное чётное простое число.
💡 После проверки на чётность достаточно рассматривать только нечётные делители.
💡 Проверять делители достаточно до квадратного корня из n.
💡 При обнаружении первого делителя можно сразу вернуть false.

Решение

public static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    if (n == 2) {
        return true;
    }

    if (n % 2 == 0) {
        return false;
    }

    for (int divisor = 3; divisor <= n / divisor; divisor += 2) {
        if (n % divisor == 0) {
            return false;
        }
    }

    return true;
}

Сначала исключаются числа, которые по определению не могут быть простыми:

if (n <= 1) {
    return false;
}

Число 2 обрабатывается отдельно:

if (n == 2) {
    return true;
}

После этого можно исключить все остальные чётные числа:

if (n % 2 == 0) {
    return false;
}

Далее проверяются только нечётные делители:

for (int divisor = 3; divisor <= n / divisor; divisor += 2)

Условие:

divisor <= n / divisor

эквивалентно проверке до √n, но не требует вычисления Math.sqrt() и избегает потенциального переполнения выражения divisor * divisor.

Если найден делитель:

if (n % divisor == 0) {
    return false;
}

число является составным.

Например, для 17 проверяются делители:

Ни один из них не делит 17 без остатка, поэтому результат — true.

Временная сложность — O(√n), дополнительная память — O(1).