Задача "2. Простоватые числа" Контеста "Региональный этап ВСОШ 2025 9-11 задачи"
Максимальное количество баллов за задачу: 30
Временной лимит: 1 с
Ограничение памяти: 512 МБ
Условие
Назовём число простоватым, если произведение цифр этого числа в десятичной системе счисления является простым числом. Например, простоватым является число 12, а число 29 не является. Требуется посчитать количество простоватых чисел от l до r, включительно. Напомним, что целое число p > 1 называется простым, если оно имеет ровно два делителя: 1 и p. Формат входных данных: Первая строка содержит одно целое число l (1 <= l <= 10^100000). Вторая строка содержит одно целое число r (l <= r <= 10^100000). Обратите внимание, что числа во вводе не помещаются в стандартные типы данных для целых чисел в большинстве языков программирования, в частности, в C++. Необходимо каким-либо специальным образом считывать входные данные, например, в виде строки. Формат выходных данных: Выведите количество простоватых чисел от l до r.
Тесты
Тест 1:
Входные данные:
42 179
Выходные данные:
10