Ранее я говорил, что задачи проекта Эйлер становятся неинтересными, так как в них повторяется одно и то же.
Но коллега по этому хобби @euler_project_c продолжает пилить задачу за задачей, и одна из них мне всё-таки показалось интересной, тем более что сложность у неё не 5% как обычно, а 15%.
Задача
Меняя первую цифру числа *3 (двузначного числа, заканчивающегося цифрой 3), оказывается, что шесть из девяти возможных значений – 13, 23, 43, 53, 73 и 83 – являются простыми числами.
При замене третьей и четвертой цифры числа 56**3 одинаковыми цифрами, получаются десять чисел, из которых семь – простые: 56003, 56113, 56333, 56443, 56663, 56773 и 56993. Число 56**3 является наименьшим числом, подставление цифр в которое дает именно семь простых чисел. Соответственно, число 56003, будучи первым из полученных простых чисел, является наименьшим простым числом, обладающим указанным свойством.
Найдите наименьшее простое число, которое является одним из восьми простых чисел, полученных заменой части цифр (не обязательно соседних) одинаковыми цифрами.
Решение
Задача устрашает количеством вложенных переборов. Во-первых, надо перебирать простые числа. Во-вторых, надо перебирать все возможные позиции любого количества одинаковых цифр в числах. В третьих, надо перебирать в каждой позиции все цифры.
Я отталкивался от того, чтобы сразу получить кусочек решения, который сократил бы остальные переборы.
Так, если я найду простое число, у которого есть несколько одинаковых цифр, то это число потенциально входит в решение. Туда же должны входить до 9 таких же чисел, у которых одинаковые цифры заменены на другие.
Следовательно, алгоритм получился такой.
- Перебирать простые числа
- Если число содержит любое количество одинаковых цифр в любых позициях, попробовать заменить эти цифры на другие. Если получилось опять простое число, попробовать заменить на другие и т.д., пока не получится простое число 8 раз
При этом возникает такой непонятный момент:
Допустим, в числе есть четыре одинаковых цифры: 1111. Надо ли менять все четыре на 2222, или поменять допустим только две: 1122 или 1212? Или три? Это ведь всё возможные варианты. Ответ: нет, надо менять именно все на все. Потому что до чисел, где есть варианты вроде 1122, мы в любом случае дойдём.
Инструментарий
Функция определения простого числа никак не изменилась с прошлых задач:
Можно применять решето Эратосфена, но уже скучно, всё было в прошлых задачах.
Для подсчёта цифр и позиций я сделал структуру, типа Digits:
Поле counters[10] хранит счётчики для каждой цифры. Поле positions[] хранит каждую цифру числа в своей позиции. Размер числа задан константой NUM_SIZE.
Подсчёт выполняет функция count_digits():
Она раскладывает число num на разряды, а получившиеся цифры записывает в соответствующие счётчики и позиции.
Поиск группы чисел выполняет функция find_group():
Цикл i проходит по счётчикам структуры. Если, к примеру, счётчик с индексом 5 равен 2, то в числе есть две цифры 5. Эти две цифры мы заменим в цикле j на 0, 1, 2, 3...9 и посмотрим, получатся ли снова простые числа. Однако заметим, что нет смысла менять цифру 5 на что-то меньшее 5. Потому что тогда получится к примеру цифра 4, которую мы встретили бы раньше. Но раз мы её уже прошли, значит и смысла в такой замене нет. Поэтому цикл j начинается с i + 1.
Здесь критично сделать возврат, как только счётчик cnt достигнет нужного значения. Иначе цикл i перейдёт к следующему набору цифр и счётчик обнулится.
Замену цифр выполняет функция replace_digit():
Она разлагает исходное число num на разряды и составляет их обратно. Но если в позиции разряда находится цифра from, то она меняется на цифру to.
Сама программа:
Перебирает числа от последнего решённого из условия задачи и до 10-значного числа (это размер NUM_SIZE). С шагом 2, потому что чётные числа заведомо не простые.
Помимо найденного числа, программа может показать все подходящие замены цифр:
Ссылка на онлайн-компилятор языка C с текстом программы
Из недоделок:
- При замене цифр нужно считать не удачные совпадения, а неудачные. Когда неудачных становится >2, можно прекращать дальнейшие проверки в текущем наборе цифр.
Но лень :) Работает вполне быстро.
Подборка всех задач: