Не простые числа содержат только 2,3,5,7 оптимизации

Question

Задача:

Вам даны два натуральных числа a и b (b - a <= 20000). Завершите функцию, которая возвращает список всех тех чисел в интервале [a, b), чьи цифры состоят из простых чисел (2, 3, 5, 7), но которые сами не являются простыми числами. </p>

Beбудьте осторожны с вашим временем!

Мое решение:

def not_primes(a, b):
    def is_prime(n):
        if not n % 2 and n > 2:
            return False

        return all(n % i for i in range(3, int(n ** 0.5) + 1, 2))

    arr = [x for x in range(a, b) if all(i in {'2', '3', '5', '7'} for i in str(x))]
    return [x for x in arr if not is_prime(x)]

Идея состояла в том, чтобы предварительно отсортировать значения и проверить, является ли оно простым или не только для чисел, составленных из 2, 3, 5 или 7.

Но для больших диапазонов это и много тестов, это медленно.

Что может быть лучшим способом улучшить производительность?

Answer 1

Некоторые предложения для быстрого решения.

1. Создать массив arr, где числа имеют только эти цифры {2,3,5,7}
2. использовать предварительно вычисленный массивis_prime используя сито, которое будет быстрее.

3. Создать новый массив только с действительными значениями в arr (которые не являются простыми)

4. Использовать бинарный поиск в новом массиве, созданном на 3-м шаге, используяА и В для подсчета