Задача №115413. Простоватые числа
Назовём число простоватым , если произведение цифр этого числа в десятичной системе счисления является простым числом. Например, простоватым является число 12, а число 29 не является.
Требуется посчитать количество простоватых чисел от \(l\) до \(r\), включительно.
Напомним, что целое число \(p > 1\) называется простым, если оно имеет ровно два делителя: \(1\) и \(p\).
Первая строка содержит одно целое число \(l\) (\(1 \le l \le 10^{100\,000}\)).
Вторая строка содержит одно целое число \(r\) (\(l \le r \le 10^{100\,000}\)).
Обратите внимание, что числа во вводе не помещаются в стандартные типы данных для целых чисел в большинстве языков программирования, в частности, в C++. Необходимо каким-либо специальным образом считывать входные данные, например, в виде строки.
Выведите количество простоватых чисел от \(l\) до \(r\).
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 19 | \(1 \le l \le r \le 10^6\) | первая ошибка | |
| 2 | 26 | \(1 \le l \le r \le 10^{18}\) | 1 | первая ошибка |
| 3 | 12 | \(l = 1\), \(r = 10^{k}\), где \(k\) (\(1 \le k \le 10^5\)) | первая ошибка | |
| 4 | 18 | \(1 \le l \le r \le 10^{1000}\) | 1, 2 | первая ошибка |
| 5 | 25 | — | 1–4 | первая ошибка |
42 179
10