Задача
Будем считать n-значное число пан-цифровым, если каждая из цифр от 1 до n используется в нем ровно один раз. К примеру, 2143 является 4-значным пан-цифровым числом, а также простым числом.
Какое существует наибольшее n-значное пан-цифровое простое число?
Решение
Предел наибольшего числа это 987654321, следовательно, при наивном подходе надо просто перебрать каждое число в этом диапазоне (почти миллиард), и проверить на панцифровость и на простоту.
Весь этот инструментарий использовался уже не раз, поэтому особо рассказать нечего, и я так и сделал.
Проблема, однако, оказалась в том, что такой перебор работал долго. Прямо очень долго.
Так что стало понятно, что надо что-то делать.
Я решил, что незачем перебирать числа последовательно, ведь нас интересуют только перестановки 123456789, поэтому вместо обычного цикла нужно делать перестановочный цикл.
Для этого опять же подойдёт любое из предыдущих решений.
Я использовал код генераторов из Задачи 32:
Конечно, он громоздкий, зато интегрировался как родной.
Программа гоняет генератор, пока его длина не превысит 9 цифр:
Я переписал функцию is_pandigital():
Раньше я держал маску занятых цифр в массиве, теперь решил сделать битовую маску.
При проверке чисел сначала проверяется панцифровость, потом простота. Если делать наоборот, программа будет работать сильно медленнее. В текущем варианте работает вполне быстро, около 130 миллисекунд.
- Стоило бы дописать генератор, чтобы была возможность двигаться в обратном направлении от больших чисел к малым. Тогда можно было бы избавиться от слежения за максимальным результатом. Просто начать с 987654321, идти вниз, и как только нашли подходящее число, сразу останавливаться.
- Стоило бы дописать генератор, чтобы он генерировал сразу панцифровые последовательности. Тогда не надо было бы привлекать функцию is_pandigital() вообще.
Всё это реализуемо, но у меня болит голова, поэтому оставил как есть.
Ссылка на онлайн-компилятор языка C с текстом программы
Пока что приходится проходить всё до конца. Причём львиная доля времени уходит на проверку "пустой" части диапазона, она начинается после 7652413 (это кстати ответ на задачу).
Что-то тут есть подозрительное, что именно после этого числа нет вообще ни одного простого панцифрового. Т.е. как только число превышает 7 знаков, то всё. Скорее всего, это можно как-то математически обосновать и ничего не проверять дальше, но мне что-то совсем ничего в голову не приходит (и болит она, опять же).
Подборка всех задач: