Подход грубой силы состоит в том, чтобы разделить n на каждое число от 2 до n-1, и если оно делится, то n является «не простым», в противном случае — «простым».

Однако после √n никакое число не делит n. Следовательно, эффективно делить n на числа от 2 до √ n, что уменьшает количество операций.

Алгоритм: Пусть n — целое число.

  • Шаг 1. Инициализируйте переменную c = 2 и s = √n.
  • Шаг 2. Если c‹=s, перейдите к шагу 3, иначе — к шагу 5.
  • Шаг 3. Если n%c == 0, прервите работу и перейдите к шагу 5, иначе перейдите к шагу 4.
  • Шаг 4: c = c+1, переход к шагу 2.
  • Шаг 5. Если c › √n, то «Prime», иначе «Not Prime».

Пример:

1) n = 6 , Целое число( √ 6) = Целое число(2,44) = 2

Шаг 1: c = 2 и s = 2

Итерация 1:

  • Шаг 2: c‹=s, т. е. 2 ‹= 2, перейдите к шагу 3.
  • Шаг 3: n%c = 6%2 == 0, поэтому перейдите к шагу 5.
  • Шаг 5: c = s(2=2), затем «Не основной».

2) n = 17, Целое число( √ 17) = Целое число(4.12) = 4

Шаг 1: c = 2 и s = 4

Итерация 1:

  • Шаг 2: c‹=s, т.е. 2 ‹= 4, перейдите к шагу 3.
  • Шаг 3: n%c = 17%2 != 0
  • Шаг 4: c = 2+1 = 3

Итерация 2:

  • Шаг 2: c‹=s, т.е. 3 ‹= 4, перейдите к шагу 3.
  • Шаг 3: n%c = 17%3 != 0
  • Шаг 4: c = 3+1 = 4

Итерация 3:

  • Шаг 2: c‹=s, т.е. 4 ‹= 4, перейдите к шагу 3.
  • Шаг 3: n%c = 17%4 != 0
  • Шаг 4: c = 4+1 = 5

Итерация 4:

  • Шаг 2. Теперь c ›=4, т.е. 5 ›= 4, переходим к шагу 5.
  • Шаг 5: c › s, т.е. 5 › 4, тогда это «Простое число»

Временная сложность:

Если n — целое число, то алгоритм выполняет операции T(n) = O( √ n), чтобы определить, является ли число простым или нет.

Код: JAVA

Первоначально опубликовано по адресу https://aanshsavla.hashnode.dev.