Алгоритм поиска простых чисел

Простые числа интересны тем, что до сих пор не выявлено какой-либо закономерности, предсказывающей их появление. Создается впечатление, что они возникают совершенно случайно, бессистемно, непредсказуемо.

Напомню, что простые числа – это числа, которые делятся без остатка только на себя и на единицу, т.е. их нельзя разложить на множители. Например: 3, 7, 11 – это простые числа. Число 9 делится на 3, поэтому не является простым.

Принято считать, что первое простое число – это 2. Число 1 не относят к множеству простых чисел, и я считаю это большой ошибкой. Да, наверное, если подходить формально к определению простого числа, то 1 нельзя считать простым, ведь оно «делится на себя». Но если следовать не букве, а, так сказать, «духу» определения, то единица является самым что ни на есть простым, т.е. неразложимым числом.

При таком подходе к определению простого числа многое становится понятным. А главное – можно создать довольно простой алгоритм поиска простых чисел.

Одним из первых алгоритмов поиска простых чисел является «решето Эратосфена». Он заключается в переборе всех натуральных чисел и вычеркивании непростых. Я предлагаю другой способ.

Я предлагаю заполнять одномерный массив (последовательность) простыми числами, начиная с первых двух простых чисел – 1 и 2.

Третье простое число (3) образуется сложением 1 и 2. Далее мы следуем такому алгоритму:

  1. Берем самый последний элемент нашей последовательности и прибавляем к нему один из предыдущих элементов (начиная с первого), и проверяем полученный результат на простоту.
  2. Если число получается непростым, т.е. делится на какой-либо из предыдущих элементов без остатка, то переходим к следующему элементу.
  3. Как только простое число получено, мы добавляем его в массив и снова начинаем перебор (переходим к шагу 1).

В итоге у нас получается такая последовательность:

1

2

3=2+1

5=3+2

7=5+2

11=7+3+1

13=11+2

…

Выяснилось, что простые числа делятся на два типа:

  1. те, которые можно представить в виде суммы или разности двух разных простых чисел (например, 7=5+2, 11=13-2),
  2. те, которые можно представить в виде суммы или разности минимум трех простых чисел (например, 47=43+3+1).

Это чем-то отдаленно похоже на деление натуральных чисел по признаку четности-нечетности.