Натуральные целые числа, чье значение больше двух, подразделяются на простые и составные.
Простое без остатка делится только на единицу и на само себя: 2, 11, 117.
Составное обладает, как минимум, тремя делителями: 4, 48, 99… Делитель — это b, на которое искомое a делится без остатка. Делители 24 — 1, 2, 3, 4, 6, 8, 12 и 24.
Любопытные факты:
- Все четные, исходя из определения, делятся на 2. Получается, двойка — единственное четное простое число.
- Единственное простое число, оканчивающееся на 5, — сама пятерка.
- Единица не относится ни к простым, ни к составным, поскольку у нее только один делитель.
Важно: любое целое число больше единицы будет или простым, или составным.
Простые числа применяют в арифметических операциях и математических алгоритмах. Например, в распределенных системах используется метод разложения по простым множителям для определения уникального идентификатора узла в сети. Также они применяются в криптографии для шифрования информации.
Для удобства использования и поиска в диапазоне 1…1000 составили специальную таблицу:
В основе теории чисел лежит Теорема Евклида, утверждающая, что существует бесконечно много простых чисел. Оригинальное доказательство выглядит следующим образом.
Дан конечный набор a, b, … z. Пусть P — их наименьшее общее кратное:
При прибавлении к произведению единицы получаем Q:
Q=P+1
Евклид утверждает, что остаток от деления на любое значение из изначального набора равен единицы. Из этого следует, что или Q — простое число, или делится на некое простое, не входящее в исходный диапазон.
В декабре 2018 года найдено очередное самое большое простое число:
Ученые утверждают, что простые числа распределены в массиве по невероятному закону, не поддающемуся попыткам установить его. К примеру, можно ответить, чему равно пятисотое из них. Для этого составляют список и смотрят, какое окажется на нужном месте. Простейший метод заключается в том, чтобы перебирать массив значений и вычеркивать составные. Современные технологии выполняют такую операцию за доли секунды, однако по сути процедура основана на методе Эратосфена, или Решете Эратосфена.
Решето Эратосфена — метод выявления простых чисел в заданном диапазоне, изобретенный древнегреческим математиком. Это надежный алгоритм, которым легко пользоваться.
Создается массив 2…50:
При ручном методе фиксируют каждое новое простое число, а затем вычеркивают его производные.
Метод Эратосфена просеивает массив, как через решето, и выдает нужный результат. Один из вариантов — сдвигаться вправо от каждого простого числа на его значение и вычеркивать составное. Таким образом, в таблице останутся искомые значения:
Графический и наглядный способ предлагает работу с прямоугольной таблицей. Для начала вычеркивают четные, за исключением двойки, проводя вертикальные линии вниз в столбцах 2, 4 и 6. Затем оставляют тройку и проводят вертикальную линию в столбце 3. На очереди пятерка. Оставляя ее, убирают кратные, проводя диагонали по направлению вниз и влево. Все кратные 7, убираются диагоналями вниз и вправо. Таблицу можно продолжать бесконечно, оперируя диагоналями от каждого следующего простого числа:
Применяемая теорема гласит: наименьший целый простой делитель b у a не может быть больше арифметического квадратного корня из a. При этом b больше единицы.
Получается, существует множитель q, чье произведение с b дает a:
При решении неравенства получается:
На практике эта теорема задает максимальное простое число внутри диапазона a…n, не превосходящее квадратный корень из n. В диапазоне 1…100 — это семерка.
Иногда определить простое это число или составное весьма затруднительно, особенно если оно состоит из не одного разряда.
Например, для 10 массив будет выглядеть следующим образом после каждой итерации:
После третьей итерации массив пуст, поэтому N=10 считается составным.
В этом способе используется принцип делимости без остатка на любое значение, отличное от единицы и искомого. Способ громоздкий, требует определенных знаний и времени, поскольку напоминает усложненный метод перебора.
Возьмем произвольное значение 349781.
Далее следует перебирать все вероятные делители. Если ни один не подойдет, 349781 — простое число. Однако в этом случае доказывается не простота числа, а его принадлежность к классу составных.
Рациональнее будет применить комбинированный метод. Отталкиваясь от теоремы из Решета Эратосфена, найдем наибольший возможный делитель:
Далее воспользуемся таблицей простых чисел до 1000 и методично проверим делимость без остатка на каждое из них. Путем перебора выясняем, что 349781 имеет следующие делители: 109 и 3209. Следовательно, оно составное.
