Как проверить, является ли число простым на Java

Введение

В этом практическом занятии (лабораторной работе) вы научитесь проверять, является ли число простым на Java. Мы начнем с реализации простого цикла для определения простоты числа.

Далее мы оптимизируем процесс проверки на простоту, используя квадратный корень из числа. Наконец, мы улучшим код, чтобы он корректно обрабатывал отрицательные и нецелые входные данные.

Реализация базового цикла проверки на простоту

На этом этапе мы напишем программу на Java для проверки, является ли заданное число простым, используя базовый цикл. Простое число - это натуральное число больше 1, которое не имеет положительных делителей, кроме 1 и самого себя.

Откройте файл HelloJava.java в редакторе WebIDE, если он еще не открыт.
Замените все содержимое файла следующим кодом:
```
import java.util.Scanner;

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

        System.out.print("Enter a positive integer: ");
        int number = scanner.nextInt();

        if (number <= 1) {
            System.out.println(number + " is not a prime number.");
        } else {
            boolean isPrime = true;
            for (int i = 2; i < number; i++) {
                if (number % i == 0) {
                    isPrime = false;
                    break; // Exit the loop early if a divisor is found
                }
            }

            if (isPrime) {
                System.out.println(number + " is a prime number.");
            } else {
                System.out.println(number + " is not a prime number.");
            }
        }

        scanner.close();
    }
}
```
Разберём новые части этого кода:
- Мы по-прежнему используем Scanner для получения ввода от пользователя.
- int number = scanner.nextInt();: Эта строка считывает целочисленное значение, введенное пользователем, и сохраняет его в переменной number.
- if (number <= 1): Мы проверяем, является ли число меньше или равным 1. Числа, меньшие или равные 1, не считаются простыми.
- boolean isPrime = true;: Мы вводим логическую (boolean) переменную isPrime и инициализируем ее значением true. Мы будем использовать ее для отслеживания того, является ли число простым.
- for (int i = 2; i < number; i++): Это цикл for. Он начинается с i равным 2 и продолжается, пока i меньше number. На каждой итерации i увеличивается на 1. Мы начинаем проверку делителей с 2, потому что 1 всегда является делителем, и мы ищем делители, отличные от 1 и самого числа.
- if (number % i == 0): Внутри цикла эта строка проверяет, делится ли number на i без остатка (остаток от деления равен 0). Если это так, значит, мы нашли делитель, отличный от 1 и самого числа.
- isPrime = false;: Если найден делитель, мы устанавливаем isPrime в false.
- break;: Эта инструкция немедленно завершает цикл for. Как только мы находим один делитель, мы знаем, что число не является простым, поэтому нет необходимости продолжать проверку.
- Наконец, мы проверяем значение isPrime и выводим, является ли число простым или нет.
Сохраните файл (Ctrl+S или Cmd+S).
Скомпилируйте модифицированную программу в терминале:
```
javac HelloJava.java
```
Если нет ошибок компиляции, будет создан файл HelloJava.class.
Запустите скомпилированную программу:
```
java HelloJava
```
Программа попросит вас ввести положительное целое число. Введите число (например, 7) и нажмите Enter. Программа сообщит, является ли число простым или нет. Попробуйте ввести разные числа, такие как 4, 11, 1 или 0, чтобы увидеть результат.
```
Enter a positive integer: 7
7 is a prime number.
```
```
Enter a positive integer: 4
4 is not a prime number.
```

Вы успешно реализовали базовый проверятель простых чисел с использованием цикла на Java!

Оптимизация проверки на простоту с использованием квадратного корня

На предыдущем этапе наш цикл проверки на простоту перебирал числа от 2 до самого числа. Хотя это работает, для очень больших чисел это может быть неэффективно. Мы можем оптимизировать этот процесс, проверяя делители только до квадратного корня из числа.

Вот почему эта оптимизация работает: если число n имеет делитель d, больший его квадратного корня (d > sqrt(n)), то должно существовать другое число d', такое что d * d' = n. Это другое число d' должно быть меньше квадратного корня (d' < sqrt(n)). Поэтому, если число имеет какие - либо делители, отличные от 1 и самого себя, то оно должно иметь хотя бы один делитель, меньший или равный его квадратному корню. Таким образом, нам нужно проверять делители только до квадратного корня.

Откройте файл HelloJava.java в редакторе WebIDE.
Измените цикл for в методе main так, чтобы он перебирал числа только до квадратного корня из числа. Замените существующий блок цикла for следующим кодом:
```
// ... (предыдущий код) ...

if (number <= 1) {
    System.out.println(number + " is not a prime number.");
} else {
    boolean isPrime = true;
    // Оптимизируем цикл, чтобы проверять до квадратного корня
    int limit = (int) Math.sqrt(number);
    for (int i = 2; i <= limit; i++) {
        if (number % i == 0) {
            isPrime = false;
            break; // Выход из цикла, если найден делитель
        }
    }

    if (isPrime) {
        System.out.println(number + " is a prime number.");
    } else {
        System.out.println(number + " is not a prime number.");
    }
}

// ... (остальной код) ...
```
Рассмотрим изменения:
- int limit = (int) Math.sqrt(number);: Мы вычисляем квадратный корень из числа number с помощью метода Math.sqrt(). Этот метод возвращает значение типа double, поэтому мы преобразуем его в int, так как наш счетчик цикла i является целым числом. Мы сохраняем это значение в переменной limit.
- for (int i = 2; i <= limit; i++): Теперь цикл перебирает числа от 2 до вычисленного значения limit (целой части квадратного корня), включая его.
Сохраните файл (Ctrl+S или Cmd+S).
Скомпилируйте оптимизированную программу в терминале:
```
javac HelloJava.java
```
Опять же, если нет ошибок, будет сгенерирован файл HelloJava.class.
Запустите скомпилированную программу:
```
java HelloJava
```
Введите разные числа, чтобы протестировать оптимизированный проверятель простых чисел. Вы должны получить те же результаты, что и раньше, но для очень больших чисел эта версия будет работать быстрее.
```
Enter a positive integer: 29
29 is a prime number.
```
```
Enter a positive integer: 100
100 is not a prime number.
```

Вы успешно оптимизировали программу проверки на простоту, уменьшив количество итераций в цикле.

Обработка отрицательных и нецелых входных данных

На предыдущих этапах наша программа предполагает, что пользователь всегда будет вводить положительное целое число. Однако в реальных приложениях пользователи могут ввести отрицательные числа, ноль или даже нечисловой текст. Наша текущая программа не обрабатывает такие случаи корректно. На этом этапе мы добавим проверки для обработки отрицательных и нецелых входных данных.

Откройте файл HelloJava.java в редакторе WebIDE.
Измените метод main так, чтобы он включал проверки на отрицательные числа и использовал цикл для обеспечения ввода пользователем допустимого положительного целого числа. Замените существующий код в методе main следующим:
```
import java.util.Scanner;
import java.util.InputMismatchException; // Импортируем этот класс

public class HelloJava {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int number = 0;
        boolean validInput = false;

        // Цикл до тех пор, пока не будет получен допустимый положительный целый ввод
        while (!validInput) {
            System.out.print("Enter a positive integer: ");
            try {
                number = scanner.nextInt();
                if (number > 0) {
                    validInput = true; // Ввод допустим, выходим из цикла
                } else {
                    System.out.println("Please enter a positive integer (greater than 0).");
                }
            } catch (InputMismatchException e) {
                System.out.println("Invalid input. Please enter an integer.");
                scanner.next(); // Считываем неверный ввод, чтобы избежать бесконечного цикла
            }
        }

        // Теперь выполняем проверку на простоту для допустимого положительного числа
        if (number <= 1) { // Эта проверка технически избыточна из-за цикла ввода, но улучшает ясность
            System.out.println(number + " is not a prime number.");
        } else {
            boolean isPrime = true;
            int limit = (int) Math.sqrt(number);
            for (int i = 2; i <= limit; i++) {
                if (number % i == 0) {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime) {
                System.out.println(number + " is a prime number.");
            } else {
                System.out.println(number + " is not a prime number.");
            }
        }

        scanner.close();
    }
}
```
Разберём новые добавления:
- import java.util.InputMismatchException;: Мы импортируем этот класс для обработки случаев, когда пользователь вводит что - то, что не является целым числом.
- int number = 0; boolean validInput = false;: Мы инициализируем переменную number и логический флаг validInput.
- while (!validInput): Это цикл while, который будет выполняться до тех пор, пока validInput равно false.
- try { ... } catch (InputMismatchException e) { ... }: Это блок try - catch. Код внутри блока try выполняется. Если возникает исключение InputMismatchException (то есть ввод не был целым числом), выполняется код внутри блока catch.
- number = scanner.nextInt();: Мы пытаемся прочитать целое число.
- if (number > 0): Внутри блока try мы проверяем, является ли введенное число положительным. Если да, мы устанавливаем validInput в true, чтобы выйти из цикла.
- System.out.println("Please enter a positive integer (greater than 0).");: Если число не является положительным, мы выводим сообщение об ошибке.
- System.out.println("Invalid input. Please enter an integer.");: Внутри блока catch, если возникает исключение InputMismatchException, мы выводим сообщение об ошибке.
- scanner.next();: Это важная строка внутри блока catch. Она считывает неверный ввод из сканера, предотвращая бесконечный цикл, когда программа постоянно пытается прочитать тот же неверный ввод.
Сохраните файл (Ctrl+S или Cmd+S).
Скомпилируйте обновленную программу:
```
javac HelloJava.java
```
Запустите программу:
```
java HelloJava
```
Теперь попробуйте ввести разные типы данных:
- Введите положительное целое число (например, 13).
- Введите отрицательное целое число (например, -5).
- Введите ноль (0).
- Введите текст (например, "hello").
Посмотрите, как программа обрабатывает эти разные входные данные, предлагая вам ввести допустимое положительное целое число до тех пор, пока вы этого не сделаете.
```
Enter a positive integer: -5
Please enter a positive integer (greater than 0).
Enter a positive integer: 0
Please enter a positive integer (greater than 0).
Enter a positive integer: hello
Invalid input. Please enter an integer.
Enter a positive integer: 17
17 is a prime number.
```

Вы успешно сделали свою программу проверки на простоту более надежной, обрабатывая отрицательные числа и нецелые входные данные с использованием цикла и обработки исключений.

Резюме

В этом практическом занятии (лабораторной работе) мы научились проверять, является ли число простым на Java. Мы начали с реализации базовой проверки на простоту с использованием цикла, который перебирает числа от 2 до числа, уменьшенного на один, и проверяет делимость. Этот первоначальный подход дал фундаментальное понимание определения простого числа и его алгоритмической реализации.

Затем мы исследовали оптимизации для повышения эффективности проверки на простоту. Это включало понимание того, что нам нужно проверять делители только до квадратного корня из числа, что значительно уменьшает количество итераций для больших входных данных. Наконец, мы решили проблему граничных случаев, обработав отрицательные числа и нецелые входные данные, чтобы сделать нашу функцию проверки на простоту более надежной и полной.