Это первая глава второй части статьи про 51 задачу из проекта Эйлера. Если вы пришли сюда, чтобы просто понять принцип задачи, а сам код хотите писать сами, то вам нужна первая часть данной статьи. Если же вы хотите увидеть решение, где я привожу и объясняю готовый код (скачать файл с готовым кодом) на python с четким ответом на задачу, а также поясняю некоторые нюансы, то оставайтесь здесь, но предварительно прочитав первую часть. Итак, начнем. Напомню формулировку задачи.
Формулировка задачи
Меняя первую цифру числа *3 (двузначного числа, заканчивающегося цифрой 3), оказывается, что шесть из девяти возможных значений - 13, 23, 43, 53, 73 и 83 - являются простыми числами.
При замене третьей и четвертой цифры числа 56**3 одинаковыми цифрами, получаются десять чисел, из которых семь - простые: 56003, 56113, 56333, 56443, 56663, 56773 и 56993. Число 56**3 является наименьшим числом, подставление цифр в которое дает именно семь простых чисел. Соответственно, число 56003, будучи первым из полученных простых чисел, является наименьшим простым числом, обладающим указанным свойством.
Найдите наименьшее простое число, которое является одним из восьми простых чисел, полученных заменой части цифр (не обязательно соседних) одинаковыми цифрами.
Функции
Для решения данной задачи нам понадобятся две функции - первая необходима просто для удобства тестирования, а вторая обязательна. Начнем с первой.
Эта функция производит поиск простых чисел в диапазоне от 3 до n и записывает их в глобальный список. Этот же список используется во второй, обязательной функции.
Эта функция находит и генерирует простые числа, начиная с числа i. Для своей работы она использует все тот же глобальный список. И если мы хотим, чтобы простые числа генерировались начиная с какого-то определенного числа, то присваиваем это число переменной i внутри функции. Тут-то как раз таки и вступает в дело первая функция, которая спокойно просчитывает все простые числа вплоть до i и формирует список, которым пользуется вторая функция.
При итоговом запуске готовой программы достаточно иметь только вторую функцию со значением переменных i = 3 и array = [2]. Однако при разработке и отладке удобно пользоваться именно двумя функциями (тем более, что производительность при этом никак не понижается).
Нюансы
Итак, нюансы. Сейчас будет сложно.
По условию задачи, нам необходимо найти такое простое число, что если мы в нем заменим несколько одинаковых цифр другими одинаковыми цифрами, то получим еще семь бо́льших простых чисел. Сколько же цифр в числе нужно заменять?
- Точно не одну. Пусть есть простое число, и пусть одна из его цифр - это единица. Пусть это число при делении на три образует остаток один (сумма цифр этого числа при делении на три образует остаток один - признак делимости числа на три), тогда, если заменить единицу из этого числа на ноль, три, шесть или девять - то полученное число уже не будет простым (будет делиться на три - по признаку делимости). Для замены остается пять цифр - 2, 4, 5, 7 и 8. Итого, с помощью замены, получаем шесть простых чисел, а нужно было восемь. (Это демонстрирует первый пример в условии задачи)
- Точно не две. Пусть опять есть простое число, и пусть теперь две его цифры - это нули. Опять таки пусть это число при делении на три образует остаток один (сумма цифр этого числа при делении на три образует остаток один - признак делимости числа на три), тогда, если заменить нули из этого числа на двойки, пятерки или восьмерки - то полученное число уже не будет простым (будет делится на три - по признаку делимости). Для замены остается шесть цифр - 1, 3, 4, 6, 7 и 9. Итого, с помощью замены, получаем семь простых чисел, а нужно было восемь. (Это демонстрирует второй пример в условии задачи)
Дальнейшие подобные размышления практически невозможны (уже не удастся провернуть фокус с делением на три), но они и не нужны, закономерность мы уловили, а значит можем предположить, что заменять нам придется три или более одинаковых цифр. Это открытие сильно упрощает код, который я буду рассматривать уже в следующей статье, ведь эта и так получилась слишком большой. Так что пока можете сходить за чаем и печенюшками. Я подожду.
Ну что, готовы? Тогда вперед ---->