Java Программа для проверки простого числа с примером

Что такое простое число?

Простое число — это натуральное число больше 1, которое делится только на 1 или на себя. Например, 11 делится только на 1 или на себя. Другие простые числа — это 2, 3, 5, 7, 11, 13, 17, и эта последовательность продолжается бесконечно.

Число больше 1, не являющееся простым, называется составным числом, поскольку его можно составить из меньших делителей. Число 9 является составным, потому что оно делится на 3 без остатка, а число 15 является составным, потому что оно делится на 3 и 5 без остатка.

Примечание: 0 и 1 не являются простыми числами. 2 — единственное четное простое число, а отрицательные значения никогда не считаются простыми.

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

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

Логика программы:

• Нам нужно разделить входное число, скажем, 17, на числа от 2 до 17 и проверить остаток. Если остаток равен 0, то число не является простым.
• Ни одно число не делится само на себя более чем на половину. Поэтому нам нужно поиска через всего numberToCheck/2Если на входе 17, то половина равна 8.5, и цикл будет перебирать значения от 2 до 8.
• Если число numberToCheck делится на другое число без остатка, флаг isPrime устанавливается в значение false и цикл завершается.

Две Java Все функции содержат весь алгоритм. Оператор деления по модулю. % возвращает остаток от деления целого числа, и break Оператор останавливает цикл, как только становится известен ответ, поэтому не выполняются лишние итерации.

Java Программа для проверки, является ли число простым или нет.

Приведённая ниже программа присваивает переменной numberToCheck значение 17 и выводит каждый шаг деления, так что вы можете проследить ход вычислений построчно. Код можно редактировать, поэтому измените значение и запустите программу ещё раз с составным числом, например, 21, чтобы увидеть противоположный результат.

public class PrimenumberToCheckCheck {

 public static void main(String[] args) {
  int remainder;
  boolean isPrime=true;
  int numberToCheck=17; // Enter the number you want to check for prime

  //Loop to check whether the number is divisible by any number other than 1 and itself
  for(int i=2;i<=numberToCheck/2;i++)
  {
   //number is divided by i
            remainder=numberToCheck%i;
            System.out.println(numberToCheck+" Divided by "+ i + " gives a remainder "+remainder);

       //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
     if(remainder==0)
     {
        isPrime=false;
        break;
     }
  }
  // Check value true or false, if isPrime is true then the number is prime otherwise not prime
  if(isPrime)
     System.out.println(numberToCheck + " is a Prime number");
  else
     System.out.println(numberToCheck + " is not a Prime number");
    }
  }

Ожидаемый результат:

17 Divided by 2 gives a remainder 1
17 Divided by 3 gives a remainder 2
17 Divided by 4 gives a remainder 1
17 Divided by 5 gives a remainder 2
17 Divided by 6 gives a remainder 5
17 Divided by 7 gives a remainder 3
17 Divided by 8 gives a remainder 1
17 is a Prime number

Цикл останавливается на 8, потому что 17, деленное на 2, в целочисленной арифметике равно 8. Поскольку остаток никогда не был равен нулю, флаг isPrime сохраняет свое начальное значение true, а в заключительном условии выводится положительный результат.

Оптимизированная проверка простых чисел с использованием метода квадратного корня.

Деление до половины числа является правильным, но неэффективным. Если делитель числа n больше его квадратного корня, то соответствующий делитель должен быть меньше квадратного корня, поэтому он уже был бы найден. Следовательно, проверка до √n дает тот же ответ с гораздо меньшим количеством итераций.

public class PrimeCheckOptimized {

    public static boolean isPrime(int n) {
        // 0, 1 and negative values are never prime
        if (n <= 1) {
            return false;
        }
        // 2 is the only even prime number
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        // test only odd divisors up to the square root
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] samples = {1, 2, 9, 17, 97};
        for (int value : samples) {
            System.out.println(value + " is prime: " + isPrime(value));
        }
    }
}

Выход:

1 is prime: false
2 is prime: true
9 is prime: false
17 is prime: true
97 is prime: true

Условие i * i <= n Это позволяет избежать вызова функции Math.sqrt с плавающей запятой, а шаг 2 пропускает каждый четный делитель. Для значения, например, 1 000 003, базовый цикл выполняет примерно 500 000 итераций, тогда как эта версия выполняет менее 500.

Проверьте простое число, введенное пользователем.

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

import java.util.Scanner;

public class PrimeCheckUserInput {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = sc.nextInt();

        boolean isPrime = number > 1;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(number + (isPrime ? " is a Prime number" : " is not a Prime number"));
        sc.close();
    }
}

Пример запуска:

Enter a number: 29
29 is a Prime number

Распространенные ошибки при написании программы для вычисления простых чисел.

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

1. Начинаем цикл с 1: Каждое целое число делится на 1, поэтому флаг немедленно устанавливается в значение false, и программа сообщает, что ни одно число не является простым.
2. Рассматривая 1 как простое число: Значение 1 имеет только один делитель, поэтому оно не соответствует определению с двумя делителями и должно возвращать false.
3. Оператор break опущен: Программа по-прежнему выдает правильный ответ, но продолжает итерации после того, как вердикт известен, что приводит к трате времени на обработку больших объемов входных данных.
4. . i <= n в качестве границы: Число всегда делится само на себя, поэтому цикл должен остановиться до достижения n.
5. Сравнивая с = вместо ==: Один знак равенства присваивает значение, а не проверяет его, что приводит к ошибке компиляции в условии if.

Сравнение методов проверки простых чисел

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

Когда необходимо классифицировать весь диапазон значений, а не одно значение, метод решета оказывается гораздо эффективнее. Наша сопутствующая программа для поиска Простое число Numbers с 1 по 100 год демонстрирует эту закономерность. Для ознакомления с аналогичными упражнениями, использующими циклы, обратитесь к следующему разделу. Последовательность Фибоначчи в Java, Java программа палиндромов, и Bubble Алгоритм сортировки в JavaНовичкам, которым необходимо освежить знания о том, как объявлять флаг и вести подсчет очков, следует ознакомиться с информацией о следующем: Java переменные в основном Java учебник.

Часто задаваемые вопросы (FAQ)