Простые и составные числа, определения, примеры, таблица простых чисел, решето Эратосфена

Простые и составные числа — определения и примеры

Натуральные целые числа, чье значение больше двух, подразделяются на простые и составные.

Простое без остатка делится только на единицу и на само себя: 2, 11, 117.

Составное обладает, как минимум, тремя делителями: 4, 48, 99… Делитель — это b, на которое искомое a делится без остатка. Делители 24 — 1, 2, 3, 4, 6, 8, 12 и 24.

Любопытные факты:

- Все четные, исходя из определения, делятся на 2. Получается, двойка — единственное четное простое число.

- Единственное простое число, оканчивающееся на 5, — сама пятерка.

- Единица не относится ни к простым, ни к составным, поскольку у нее только один делитель.

Важно: любое целое число больше единицы будет или простым, или составным.

Таблица простых чисел до 1000

Простые числа применяют в арифметических операциях и математических алгоритмах. Например, в распределенных системах используется метод разложения по простым множителям для определения уникального идентификатора узла в сети. Также они применяются в криптографии для шифрования информации. 

Для удобства использования и поиска в диапазоне 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 — это семерка.

Данное число простое или составное?

Иногда определить простое это число или составное весьма затруднительно, особенно если оно состоит из не одного разряда.

Принцип массива

1. Создаем массив от 2 до N.
2. Инициализируем переменную p = 2.
3. Удаляем из массива все кратные p (то есть удаляем все, что делится на p с остатком). Например, если p = 2, то удалим 4, 6, 8, 10.
4. Увеличиваем p на 1. Если p все еще является простым числом (то есть не было удалено ранее), то возвращаемся к шагу 3. Иначе переходим к шагу 5.
5. Проверяем, остались ли в массиве значения. Если да, то берем следующее по величине и переходим к шагу 3. В противном случае завершаем работу алгоритма.
6. N будет считаться простым, если после выполнения алгоритма оно осталось в массиве. Иначе, оно будет считаться составным.

Например, для 10 массив будет выглядеть следующим образом после каждой итерации:

• Итерация 1 (p = 2): [2, 3, 5, 7, 9]
• Итерация 2 (p = 3): [2, 3, 5, 7]
• Итерация 3 (p = 5): [2, 3, 5]

После третьей итерации массив пуст, поэтому N=10 считается составным.

Использование признаков делимости

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

Возьмем произвольное значение 349781.

1. Оно оканчивается на 1, то есть точно не делится без остатка на 2 и 5.
2. Посчитаем сумму цифр и проверим на делимость на 3 и 9. Сумма цифр — 32, она не делится без остатка ни на 3, ни на 9.
3. 349781 будет делиться без остатка на 11, если сумма четных цифр равна сумме нечетных цифр или же разность между ними кратна 11. Сумма цифр на нечетных местах: 3+9+8=20. Сумма цифр на четных местах: 4+7+1=12. Проведя нужные вычисления, понимаем: искомое число на 11 не делится.

Далее следует перебирать все вероятные делители. Если ни один не подойдет, 349781 — простое число. Однако в этом случае доказывается не простота числа, а его принадлежность к классу составных.

Комбинированный метод

Рациональнее будет применить комбинированный метод. Отталкиваясь от теоремы из Решета Эратосфена, найдем наибольший возможный делитель:

Далее воспользуемся таблицей простых чисел до 1000 и методично проверим делимость без остатка на каждое из них. Путем перебора выясняем, что 349781 имеет следующие делители: 109 и 3209. Следовательно, оно составное.