Доброго времени суток, читатель! Решая 51 задачу из проекта Эйлера, я столкнулся с проблемой, что в рунете нет решения этой задачи. Все, что мне удалось найти - это форум на корявом русском языке (по всей видимости перевод с английского форума), где я почерпнул принцип решения, но ни ответа, ни самого кода там не было, а также сайт на английском языке, где был код на C++, но, к сожалению, ни английского, ни C++ я не знаю. Поэтому я хочу поделиться своим решением с вами, дабы, возможно, кому-то помочь, а также выслушать конструктивную критику.
Немного о себе.
Мне 15 лет, учусь в 10 классе. Занимаюсь программированием на PHP, JavaScript и Python, решаю некоторые задачки из проекта Эйлера на последнем языке. Недавно я подумал, почему бы не размещать свое решение на Дзене, таким образом я могу кому-то помочь, лучше закреплю материал сам, а также, возможно, получу критику, которая позволит улучшить мое решение. Одни плюсы! Что ж, тогда начнем!
Формулировка задачи
Меняя первую цифру числа *3 (двузначного числа, заканчивающегося цифрой 3), оказывается, что шесть из девяти возможных значений - 13, 23, 43, 53, 73 и 83 - являются простыми числами.
При замене третьей и четвертой цифры числа 56**3 одинаковыми цифрами, получаются десять чисел, из которых семь - простые: 56003, 56113, 56333, 56443, 56663, 56773 и 56993. Число 56**3 является наименьшим числом, подставление цифр в которое дает именно семь простых чисел. Соответственно, число 56003, будучи первым из полученных простых чисел, является наименьшим простым числом, обладающим указанным свойством.
Найдите наименьшее простое число, которое является одним из восьми простых чисел, полученных заменой части цифр (не обязательно соседних) одинаковыми цифрами.
Принцип решения
Генерируя простые числа с помощью функции, мы проверяем, есть ли в данном числе повторяющиеся цифры, и если есть, добавляем это число в список, который является значением в словаре, ключом к которому выступает строка, содержащая позиции повторяющейся цифры, а также само число, из которого выкинули эти повторяющиеся цифры. Далее, как только в списке набирается восемь элементов, выводим на экран меньший из них.
Рассмотрим принцип решения на примере чисел из задачи.
Сгенерировалось простое число 56003. В нем есть повторяющаяся цифра 0. Значит, это число нужно добавить в список в словаре. Такая пара ключ-значение у нас получится в итоге:
'23563': [56003]
Строка '23563' означает, что в числах, которые находятся в списке, повторяющийся элемент находится на позиции 2 и 3 (если число 56003 превратить в список, то ноль будет находится на 2 и 3 позиции), а само число без повторяющихся цифр будет выглядеть как 563. Таким образом, если мы применим данный алгоритм и к другим числам из задачи (56113, 56333, 56443, 56663, 56773 и 56993), мы получим следующую пару ключ-значение в нашем словаре:
'23563': [56003, 56113, 56333, 56443, 56663, 56773, 56993]
Таким образом, "Число 56**3 является наименьшим числом, подставление цифр в которое дает именно семь простых чисел. Соответственно, число 56003, будучи первым из полученных простых чисел, является наименьшим простым числом, обладающим указанным свойством", - данная формулировка из задачи как нельзя лучше подходит для объяснения полученного результата.
Итак, мы разобрали алгоритм для семи простых чисел, а по условию задачи мы должны найти число XX***XXX (общее количество цифр и количество цифр для замены не известно), которое при замене звездочек одинаковыми цифрами выдает уже восемь простых чисел. Принцип работы алгоритма абсолютно такой же, хотя есть небольшие нюансы. Если вы пришли сюда, чтобы просто понять принцип задачи, а сам код хотите писать сами, то самое время открывать редактор кода! Если же вы хотите увидеть решение, то читайте вторую часть этой статьи, где я привожу и объясняю готовый код на python с четким ответом на задачу, а также поясняю те самые нюансы.
А на этом все! Подписывайтесь на канал и читайте предыдущую статью. До скорых встреч!