Что значит простые делители чисел

Делители и кратные

В данном уроке мы рассмотрим такие понятия как делители и кратные.

Что такое делитель?

Мы знаем, что делитель это число, показывающее на сколько частей нужно разделить делимое. Например, в выражении 8 : 2 = 4, делителем является число 2. Это число показывает на сколько частей нужно разделить число 8. После разделения получается ответ 4. Как видно из примера, число 8 делится на число 2 без остатка. Говорят, что число 2 является делителем числа 8.

Пример 1. Число 2 является делителем числа 8, поскольку 8 делится на 2 без остатка:

Пример 2. Число 3 является делителем числа 9, поскольку 9 делится на 3 без остатка:

Пример 3. Число 4 не является делителем числа 10 поскольку 10 не делится на 4 без остатка:

10 : 4 = 2 (2 в остатке)

Определение. Делителем числа а называется число, на которое число а делится без остатка.

Делителем числа 12 называется число, на которое 12 делится без остатка.

Попробуем перечислить эти числа:

Все эти числа являются делителями числа 12, поскольку число 12 делится на них без остатка. Покажем это:

12 : 1 = 12
12 : 2 = 6
12 : 3 = 4
12 : 4 = 3
12 : 6 = 2
12 : 12 = 1

Кратные числа

Если какое-нибудь число без остатка разделилось на другое, то его называют кратным этого числа. Например, 6 без остатка делится на 3. Поэтому 6 является кратным числа 3

Определение. Кратным числа а называется число, которое делится без остатка на а.

Кратным числа 5 называется число, которое делится без остатка на 5 .

У любого числа бесконечно много кратных. Например, первыми кратными числа 5, являются числа 5, 10, 15, 20, 25. Все они кратны 5, поскольку делятся на 5 без остатка:

5 : 5 = 1
10 : 5 = 2
15 : 5 = 3
20 : 5 = 4
25 : 5 = 5

Признаки делимости чисел

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

Признак делимости на 10

Любое число, которое оканчивается нулем, делится без остатка на 10. Чтобы получить частное, достаточно отбросить цифру 0 в делимом.

Например, 380 : 10 = 38. Мы просто отбросили последний ноль в числе 380.

В случае, если мы имеем выражение такого вида 385 : 10, то получится 38 и 5 в остатке, поскольку 380 : 10 = 38, а пятерка это остаток, который не разделился.

Таким образом, если число оканчивается цифрой 0, то оно делится без остатка на 10. Если же оно оканчивается другой цифрой, то оно не делится без остатка на 10. Остаток в этом случае равен последней цифре числа. Действительно, в примере 385 : 10 = 38 (5 в остатке), остаток равен последней цифре в числе 385, то есть пятерке.

Признак делимости на 5 и на 2

Любое число, которое оканчивается нулем, делится без остатка и на 5, и на 2.

Признак делимости на 5

Если число оканчивается цифрой 0 или 5, то оно делится без остатка на 5.

Признак делимости на 3

Число делится на 3, если сумма цифр этого числа делится на 3. Например, рассмотрим число 27, сумма его цифр 2 + 7 = 9. Девять, как мы знаем делится на 3, значит и 27 делится на 3:

Признак делимости на 9

Число делится на 9, если сумма его цифр делится на 9. Например, рассмотрим число 18. Сумма его цифр 1 + 8 = 9. Девять делится на девять, значит и 18 делится на 9

Рассмотрим число 846. Сумма его цифр 8 + 4 + 6 = 18. Восемнадцать делится на девять, значит и 846 делится на 9:

Чётные и нечётные числа

Чётным называется число, которое делится без остатка на 2. Например, число 20 является четным, поскольку оно делится без остатка на 2:

Нечётным называется число, если при его делении на 2, остаётся остаток 1. Например число 21 является нечетным, поскольку после его деления на 2 остается остаток 1:

21 : 2 = 10 (1 в остатке)

Как распознать чётное число от нечетного, не выполняя деления на 2? Очень просто. Из однозначных чисел чётными являются числа 0, 2, 4, 6, 8, а нечетными являются 1, 3, 5, 7, 9. Если число оканчивается чётной цифрой, то это число является чётным. Если число оканчивается нечетной цифрой, то это число является нечетным.

Например, число 308 чётно, поскольку оно оканчивается чётной цифрой. Число 1024 тоже четно, поскольку оканчивается четной цифрой.

А числа 305 и 1027 являются нечётными, поскольку они оканчиваются нечётными цифрами.

Простые и составные числа

Простым называется число, которое делится без остатка на единицу и на само себя. Другими словами, имеет только два делителя. Например, число 5 делится без остатка на единицу и на само себя:

Значит, число 5 является простым числом.

Составным же называется число, которое имеет два и более делителя. Например, число 4 составное, поскольку у него два и более делителя: 4, 2 и 1

Значит, число 4 является составным числом.

Разложение составного числа на простые множители

Любое составное число можно разложить на простые множители. Чем-то похожим мы занимались в уроке замены в выражениях. Из этого урока мы узнали, что любое число, входящее в выражение, можно заменить на то же самое, но записанное в другом виде.

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

Разложим число 4 на простые множители. Для этого соберем данное число из других чисел, при этом соединим их знаком умножения (×). Число 4 состоит из чисел 2 и 2. Эти два числа и являются простыми множителями, из которых состоит число 4

Разложим на множители число 6. Число 6 можно собрать из чисел 2 и 3. Эти два числа и являются простыми множителями, из которых состоит число 6

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

Например, разложим число 180 на простые множители. Число 180 это два множителя 18 и 10

Теперь раскладываем множители 18 и 10 на другие множители:

Теперь раскладываем выделенную синюю шестерку. Это последний большой множитель, который можно разложить на простые множители:

Теперь собираем все простые множители вместе:

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

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

При разложении числа этим способом, используют признаки делимости, такие как: признаки делимости на 2, на 3, на 5 и другие.

Например, разложим предыдущее число 180 этим способом.

Проводим вертикальную линию и слева записываем первое делимое 180

Теперь применяем признаки делимости. В первую очередь проверяем делится ли 180 на 2. Если делится, то нужно записать эту двойку справа от вертикальной линии.

180 делится на 2, поскольку 180 оканчивается нулём. Записываем двойку справа от вертикальной линии:

Теперь делим 180 на 2 и получаем второе делимое 90. Записываем это делимое слева от вертикальной линии:

Теперь делим 90. Снова применяем признаки делимости. Проверяем делится ли 90 на 2.

90 делится на 2, поскольку 90 оканчивается нулём. Записываем двойку справа от вертикальной линии:

Теперь делим 90 на 2, получаем третье делимое 45. Записываем это делимое слева от вертикальной линии:

Теперь делим 45. Снова применяем признаки делимости. Проверяем делится ли 45 на 2.

45 на 2 не делится. Тогда проверяем делится ли 45 на 3.

45 делится на 3, поскольку сумма цифр 4 и 5 делится на 3. Записываем тройку справа от вертикальной линии:

Делим 45 на 3, получаем четвёртое делимое 15. Записываем это делимое слева от вертикальной линии:

Теперь делим 15. Проверяем делится ли 15 на 2.

15 не делится на 2. Тогда проверяем делится ли 15 на 3.

15 на 3 делится, поскольку сумма цифр 1 и 5 делится на 3. Записываем тройку справа от вертикальной линии:

Делим 15 на 3, получаем пятое делимое 5. Записываем пятёрку слева от вертикальной линии:

Теперь делим 5. Проверяем делится ли 5 на 2.

5 не делится на 2. Тогда проверяем делится ли 5 на 3.

5 не делится на 3. Тогда проверяем делится ли 5 на 5.

5 делится на 5. Записываем эту пятёрку справа от вертикальной линии:

Делим 5 на 5, получаем шестое делимое 1. Записываем эту единицу слева от вертикальной линии:

На этом деление завершается, поскольку мы достигли единицы. Делители, которые записывают справа от вертикальной линии должны быть простыми числами. Поэтому, когда делимое 5 не разделилось на 2, а затем не разделилось на 3, мы попробовали разделить его на 5, не пробуя разделить на 4, поскольку 4 является не простым, а составным числом.

Теперь переписываем в один ряд все делители, которые записаны справа от вертикальной линии. Они и будут разложением числа 180 на простые множители. Желательно записывать их, начиная с самых малых. Это позволяет упорядочить их по возрастанию:

Не расстраивайтесь, если будете испытывать затруднения при разложении чисел на простые множители. Эта тема требует немного практики. Для тренировки можете разложить на простые множители следующие числа: 256, 378, 512.

Нахождение делителей числа

В начале данного урока было сказано, что делителем называется число, на которое другое число делится без остатка.

Например, число 2 является делителем числа 6, поскольку число 6 можно без остатка разделить на 2

6 : 2 = 3

Ещё делителем числа 6 является число 3

6 : 3 = 2

Ещё делителем числа 6 является число 1

6 : 1 = 6

Наконец, делителем числа 6 является само это число

6 : 6 = 1

Перечислим все делители числа 6

1, 2, 3, 6

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

Пример 1. Найти делители числа 12

Во-первых, единица является делителем любого числа. Пусть и у нас первым делителем числа 12 будет 1

Теперь раскладываем число 12 на простые множители:

Получили разложение 2 × 2 × 3.

В процессе разложения числа 12 на простые множители, мы делили его на числа 2 и 3. На них число 12 разделилось без остатка, значит они тоже являются делителями числа 12. Внесём эти два числа в нашу таблицу делителей:

Чтобы получить остальные делители числа 12, нужно найти все возможные произведения его простых множителей между собой. Получаемые в результате ответы и будут остальными делителями числа 12.

Число 12 мы разложили на простые множители 2 × 2 × 3. Найдём все возможные произведения этих простых множителей между собой. Первое произведение это 2 × 2. Это произведение равно 4

Занесём число 4 в нашу таблицу делителей

Следующее возможное произведение из простых множителей числа 12 это произведение 2 × 3. Данное произведение равно 6. Занесём число 6 в нашу таблицу делителей:

Последнее возможное произведение из простых множителей числа 12 это произведение из всех его множителей, а именно 2 × 2 × 3. Это произведение равно 12. Занесём число 12 в нашу таблицу делителей:

Таким образом, делителями числа 12 являются числа 1, 2, 3, 4, 6, 12.

На основании приведённого примера можно сформировать правило для нахождения делителей числа:

Чтобы найти делители числа, нужно:

Пример 2. Найти делители числа 6

Первым делителем числа 6 запишем единицу:

Теперь разложим число 6 на простые множители:

Выпишем из полученного разложения те множители, которые являются делителями числа 6. Видим, что это множители 2 и 3. Они будут следующими делителями числа 6. Допишем их к нашим делителям:

1, 2, 3

1, 2, 3, 6

Источник

Инструменты пользователя

Инструменты сайта

Боковая панель

Навигация

Загрузки всякие

Связь

Содержание

Простые числа. Делители

Из книги Паоло Джордано The Solitude of Prime Numbers («Одиночество простых чисел»):

Простые числа делятся только на единицу и самих себя. Они занимают свое место в бесконечном ряду простых чисел, которые, как и остальные числа, зажаты между двумя другими, но на один шаг дальше, чем предыдущие. Эти числа подозрительны и одиноки, и Маттиа казалось, что они волшебные. Иногда он думал, что они очутились в этом ряду по ошибке, как жемчужины, нанизанные на нитку ожерелья. А порой ловил себя на мысли, что они тоже предпочли бы быть обычными числами, однако по какой-то причине не сложилось. […]

Простые числа — атомы арифметики. Согласно греческому происхождению слова «атом», простые числа являются «атомными», то есть «неделимыми». И подобно тому как все сложено из атомов, каждое число слагается из простых чисел. Например, 60 равно 2 × 2 × 3 × 5. Мы говорим, что 60 — это составное число, и его можно представить в виде произведения простых множителей 2 (дважды), 3 и 5.

А как быть с 1? Это простое число? Нет. И когда мы поймем это, то узнаем, почему 1 — самое одинокое число, даже более одинокое, чем любое простое число.

Простые числа

Число называется простым, если оно делится только на 1 и само на себя.

Является ли заданное число простым можно проверить, последовательно деля его на все натуральные числа, меньшие его.

Как определить, является ли данное целое число простым? В теории достаточно перебрать все возможные потенциальные делители и убедиться, что остаток от деления всегда будет отличен от нуля. Но на практике определение простых чисел требует объемных вычислений: представьте, что вам нужно найти делители числа, состоящего, например, из миллиона цифр. Эта задача неподвластна современным компьютерам.

Последовательность простых чисел начинается так:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, …

Следующий вопрос звучит так: существуют ли общие формулы, позволяющие получить все простые числа или хотя бы некоторые из них? Так, выражения n² и 7n позволяют найти все квадраты и все числа, кратные 7, соответственно (для этого достаточно заменить n натуральными числами). Существует ли математическая формула, результатом которой для каждого n будет простое число? Такой формулы не существует, поскольку простые числа поистине загадочны. Можно даже сказать, что они распределены случайным образом.

Я уже говорил, что для простых чисел не существует никакой формулы, никакой комбинации алгебраических операций над n, выполняя которые можно было бы получить очередное, п-ое простое число. Многие люди впадали в заблуждение на этот счет, достигнув некоторых первоначальных успехов. Хорошо иллюстрирует подобные заблуждения шуточная поговорка, известная любому студенту-математику. В ней говорится о трех способах доказательства того, что все нечетные числа простые:

Инженер, как говорится, может смеяться последним, поскольку математики в своих поисках больших простых чисел все больше должны полагаться на компьютеры.

Фильм Куб

Составные числа

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

Таким образом, все натуральные числа разбиваются на три класса: единицу (имеющую один делитель), простые числа (имеющие два делителя) и составные числа (имеющие больше двух делителей).

Теорема. Каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей.

$$1200 = 2^4 × 3^1 × 5^2 = 3 × 2 × 2 × 2 × 2 × 5 × 5 = 5 × 2 × 3 × 2 × 5 × 2 × 2 = etc.$$

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

Бесконечность множества простых чисел

Возможно ли распознать простое число, как говорится, с первого взгляда? Если вы зачерпнули в сито сразу много чисел, сверкнет ли среди них простое, как золотой самородок? Некоторые считают, что да. Например, числа, оканчивающиеся на 1, часто оказываются искомыми, скажем, такие как 11, 31, 41. Однако при этом следует быть осторожным и не принять фальшивое золото за чистое, как, скажем, 21 или 81. По мере роста величины чисел, единица на конце все чаще вводит нас в заблуждение. Создается даже впечатление будто простые числа в конце концов просто исчезают, как полагали некоторые древние греки. Существует ли последнее, самое большое по величине простое число?

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом:

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

НОВИЧОК: Эй, мистер! Как далеко вниз по течению заходят простые числа?

СТАРОЖИЛ: До самого моря Бесконечности, парень.

НОВИЧОК: Я вам не верю. Мы здесь на уровне миллионов, а мне еще ни разу не повезло за целый день.

СТАРОЖИЛ: Эх, молодежь, вам нужно все объяснять! Смотри, допустим, ты дошел до последнего простого числа. После него их уже не существует, так?

СТАРОЖИЛ: Назовем его n. Составим произведение из всех простых чисел вплоть до n. Это будет 2х3х5х7х…n. Теперь прибавим к произведению 1 и назовем это число p.

НОВИЧОК: Вот оно что! Значит, вы правы, им конца нет.

СТАРОЖИЛ: Так-то вот. Ну ладно, чего стоишь без дела, помоги-ка мне с этим промывным желобом.

Проблемы

Гипотеза Гольдбаха

Письмо Гольдбаха Эйлеру, датированное 7 июня 1742 (Латынь-Немецкий).

С простыми числами связан ряд проблем, на протяжении десятилетий и даже веков не поддающихся решению. Одна из таких проблем — гипотеза Гольдбаха-Эйлера, сформулированная в XVIII веке: любое четное число, большее двух, можно представить в виде суммы двух простых чисел. Эта гипотеза до сих пор не доказана и не опровергнута.

Пример. 100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53

Схематическое разбиение нескольких первых четных чисел в сумму простых

Если бинарная гипотеза Гольдбаха неверна, то существует алгоритм, который рано или поздно обнаружит её нарушение.

Число способов записать четное число n как сумму двух простых (4 ≤ n ≤ 1,000,000)

Отыскание простых чисел

Решето Эратосфена

Решето Эратосфена — простой алгоритм нахождения всех простых чисел до некоторого целого числа n, путём вычёркивания всех чисел которые делятся на простой делитель: 2, 3, 5, 7 и т.д. Пускай нам нужно отыскать простые числа в промежутке от единицы до некоторого N ≤ 10^6. Мы заводим массив на N элементов и заполняем его true. Затем последовательно проходим по нему до корня из N, и встречая true, вычеркиваем все числа с этим шагом до N.

Решето только по нечётным числам: поскольку все чётные числа, кроме 2, — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами. Во-первых, это позволит вдвое сократить объём требуемой памяти. Во-вторых, это уменьшит количество выполняемых алгоритмом операций (примерно вдвое). Это можно обобщить на числа взаимно простые с 3, 5 и т. д.

Решето Аткина

Заявленная авторами асимптотическая скорость работы алгоритма соответствует скорости лучших ранее известных алгоритмов просеивания, но в сравнении с ними решето Аткина требует меньше памяти.

Интервалы между простыми числами

Интервалы между простыми числами — это разности между двумя последовательными простыми числами.

Первые 30 интервалов между простыми числами следующие:

1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14

Существуют сколь угодно большие интервалы между простыми числами. Наибольший известный интервал между простыми числами — это интервал длины 337446.

Насколько быстро простые числа разрежаются по течению реки Континуума? Из первых 10 чисел 4 являются простыми, таким образом их доля составляет 40%. В первой сотне их содержание падает до 25%, и оно продолжает падать с ростом величины чисел более или менее регулярно. В общем количество простых чисел до n включительно приблизительно равно n/ln(n). В данном случае это приближение является асимптотическим. Другими словами, если количество простых чисел, меньших либо равных n, обозначить р(n), то отношение р(n) к величине n/logn все ближе приближается к 1, по мере того как n становится все больше и больше. Таким образом, вниз по течению Континуума простые числа разрежаются пропорционально натуральному логарифму от n.

Репьюниты

Википедия: Числа, состоящие из 2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343 единиц, являются простыми

Простые палиндромы

Палиндромами называются числа, которые справа налево и слева направо читаются одинаковым образом, например, 30103. Среди таких чисел тоже встречаются простые.

Ясно, что любой простой палиндром состоит из нечётного количества цифр (за исключением числа 11), так как любой палиндром с чётным количеством цифр всегда делится на 11. Первыми простыми палиндромами являются такие числа:

2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311,…

Простые числа-близнецы

Математики давно обратили внимание, что распределение простых чисел в бесконечном числовом пространстве имеет определённые закономерности. В частности, странным феноменом выступают простые числа-близнецы, которые отличаются друг от друга на 2. Чем больше количество знаков, тем реже встречаются числа-близнецы, но всё равно они продолжают встречаться снова и снова.

В оригинальной версии гипотеза гласит, что существует бесконечное количество простых чисел-близнецов. Это предположение до сих пор никто не доказал и не опроверг.

Другими словами, среднее расстояние между числами будет приближаться к бесконечности, по мере роста количества разрядов, но при этом всегда будут встречаться простые числа, удалённые друг от друга не более чем на 70 млн, что просто удивительно.

И можно довольно несложно указать диапазон в 70 млн, в котором нет ни одного простого числа: (70млн+1)! + 2, (70млн+1)! + 3, (70млн+1)! + 4,…, (70млн+1)! + (70млн+1).

Первые простые числа-близнецы:

Постулат Бертрана

Один из интереснейших фактов о простых числах: между натуральными n и 2n всегда найдётся простое число.

Если n — натуральное, то существует простое p, такое, что n

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

Тесты простоты

Вопрос определения того, является ли натуральное число N простым, известен как проблема простоты.

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

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

Перебор делителей

Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число i равен 0, то i является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на i и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел n объявляется простым.

Для ускорения перебора часто не проверяются чётные делители, кроме числа 2, а также делители, кратные трём, кроме числа 3. При этом тест ускоряется в три раза, так как из каждых шести последовательных потенциальных делителей необходимо проверить только два, а именно вида 6·k±1, где k — натуральное число.

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

Довольно неожиданно, что существует ряд способов проверить простоту числа, не находя его делителей.

Тест Миллера

Тест Миллера — Рабина разработан в 1976 г. Алгоритм Миллера гарантированно распознает простые и составные числа при условии выполнения недоказанной расширенной гипотезы Римана. Алгоритм Миллера — Рабина не зависит от справедливости гипотезы, но является вероятностным.

Как и тесты Ферма и Соловея — Штрассена, тест Миллера — Рабина опирается на проверку ряда равенств, которые выполняются для простых чисел. Если хотя бы одно такое равенство не выполняется, это доказывает что число составное.

Идея теста заключается в том, чтобы проверять для случайно выбранных чисел, являются ли они свидетелями простоты числа. Если на определённом шаге алгоритма было проверено k чисел, и все они оказались свидетелями простоты, то вероятность того, что число составное не более (1/4)^k.

Быть может, Бог не играет в кости со Вселенной, но с простыми числами определенно что-то не так.

Некоторые простые числа

Задача. Найти простые числа, которые остаются простыми после вычеркивания одной цифры?

Например, 719 образует простые числа 71, 19 и 79.

Источник