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

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

Пример 1: проверка простого числа с помощью цикла for

Проверяем, делится ли число на какое-нибудь число от 2 до num/2. Если делится — значит, оно не простое.

public class Main {

  public static void main(String[] args) {

    int num = 29;
    boolean flag = false;

    // 0 and 1 are not prime numbers
    if (num == 0 || num == 1) {
        flag = true;
    }

    for (int i = 2; i <= num / 2; ++i) {

      // condition for nonprime number
      if (num % i == 0) {
        flag = true;
        break;
      }
    }

    if (!flag)
      System.out.println(num + " is a prime number.");
    else
      System.out.println(num + " is not a prime number.");
  }
}

Вывод:

29 is a prime number.

В этой программе цикл for определяет, простое ли число num.

Примечание

Перебор идёт от 2 до num/2, потому что число не может делиться на число, большее своей половины (кроме самого себя).

Внутри цикла проверяется, делится ли num на i:

• Если делится — флагу flag присваивается true, и мы выходим из цикла через break. Это значит, что num не простое.

• Если ни на одно число не разделилось — flag остаётся false, и num — простое.

Пример 2: проверка простого числа с помощью цикла while

Тот же алгоритм можно записать через while.

public class Main {

  public static void main(String[] args) {

    int num = 33, i = 2;
    boolean flag = false;

    // 0 and 1 are not prime numbers
    if (num == 0 || num == 1) {
        flag = true;
    }

    while (i <= num / 2) {

      // condition for nonprime number
      if (num % i == 0) {
        flag = true;
        break;
      }

      ++i;
    }

    if (!flag)
      System.out.println(num + " is a prime number.");
    else
      System.out.println(num + " is not a prime number.");
  }
}

Вывод:

33 is not a prime number.

Цикл while работает, пока i <= num/2. На каждой итерации проверяется, делится ли num на i без остатка, и i увеличивается на 1.