Простые и составные числа, определения, примеры, таблица простых чисел, решето Эратосфена
Простые и составные числа — определения и примеры
Натуральные целые числа, чье значение больше двух, подразделяются на простые и составные.
Простое без остатка делится только на единицу и на само себя: 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 — это семерка.
Данное число простое или составное?
Иногда определить простое это число или составное весьма затруднительно, особенно если оно состоит из не одного разряда.
Принцип массива
- Создаем массив от 2 до N.
- Инициализируем переменную p = 2.
- Удаляем из массива все кратные p (то есть удаляем все, что делится на p с остатком). Например, если p = 2, то удалим 4, 6, 8, 10.
- Увеличиваем p на 1. Если p все еще является простым числом (то есть не было удалено ранее), то возвращаемся к шагу 3. Иначе переходим к шагу 5.
- Проверяем, остались ли в массиве значения. Если да, то берем следующее по величине и переходим к шагу 3. В противном случае завершаем работу алгоритма.
- 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, то есть точно не делится без остатка на 2 и 5.
- Посчитаем сумму цифр и проверим на делимость на 3 и 9. Сумма цифр — 32, она не делится без остатка ни на 3, ни на 9.
- 349781 будет делиться без остатка на 11, если сумма четных цифр равна сумме нечетных цифр или же разность между ними кратна 11. Сумма цифр на нечетных местах: 3+9+8=20. Сумма цифр на четных местах: 4+7+1=12. Проведя нужные вычисления, понимаем: искомое число на 11 не делится.
Далее следует перебирать все вероятные делители. Если ни один не подойдет, 349781 — простое число. Однако в этом случае доказывается не простота числа, а его принадлежность к классу составных.
Комбинированный метод
Рациональнее будет применить комбинированный метод. Отталкиваясь от теоремы из Решета Эратосфена, найдем наибольший возможный делитель:
Далее воспользуемся таблицей простых чисел до 1000 и методично проверим делимость без остатка на каждое из них. Путем перебора выясняем, что 349781 имеет следующие делители: 109 и 3209. Следовательно, оно составное.