Нахождение чисел от а до b, не кратных х до у

Вам нужно только проверить простые значения в диапазоне возможных делителей - например, если значение не делится на 2, оно также не будет делиться ни на одно кратное 2; аналогично для любого другого простого числа и простого кратного. Таким образом, в вашем примере вы можете проверить 2, 3, 5 - вам не нужно проверять 4, потому что все, что делится на 4, должно делиться на 2. Следовательно, более быстрым подходом было бы вычисление простых чисел в любом интересующем вас диапазоне, а затем просто вычислить, какие значения они делят.

Еще одно ускорение заключается в добавлении каждого значения в интересующем вас диапазоне к set: когда вы обнаружите, что оно делится на число в вашем диапазоне, удалите его из набора. Затем вы должны тестировать только те числа, которые остались в наборе — это остановит многократное тестирование чисел.

Если мы объединим эти два подхода, мы увидим, что мы можем создать set всех значений (например, набор со всеми значениями от 1 до 10) и просто удалить кратные каждому простому числу во втором диапазоне из этого набора.

Редактировать: как указал Паташу, это не совсем сработает, если простое число, которое делит данное значение, отсутствует в наборе. Чтобы исправить это, мы можем применить алгоритм, аналогичный приведенному выше: создать set со значениями [a, b], для каждого значения в set удалить все его кратные. Итак, для примера, приведенного ниже в комментариях (с [3, 6]), мы начнем с 3 и удалим его кратные в наборе - так что 6. Следовательно, оставшиеся значения, которые нам нужно проверить, будут [3, 4, 5], что нам и нужно в данном случае.

Edit2: Вот действительно взломанная, дрянная реализация, которая не была оптимизирована и имеет ужасные имена переменных:

def find_non_factors():
    a = 1
    b = 1000000
    x = 200
    y = 1000

    z = [True for p in range(x, y+1)]
    for k, i in enumerate(z):
        if i:
            k += x
            n = 2
            while n * k < y + 1:
                z[(n*k) - x] = False
                n += 1

    k = {p for p in range(a, b+1)}

    for p, v in enumerate(z):
        if v:
            t = p + x
            n = 1
            while n * t < (b + 1):
                if (n * t) in k:
                    k.remove(n * t)
                n += 1

    return k

Попробуйте свою оригинальную реализацию с этими числами. На моем компьютере это занимает > 1 минуты. Эта реализация занимает менее 2 секунд.

Предупреждение об окончательной оптимизации: не оптимизируйте преждевременно. Каждый раз, когда вы пытаетесь оптимизировать код, профилируйте его, чтобы убедиться, что он нуждается в оптимизации, и профилируйте оптимизацию на том же типе данных, для которого вы собираетесь его оптимизировать, чтобы убедиться, что это ускорение. Почти весь код не нуждается в оптимизации. оптимизация, просто чтобы дать правильный ответ.

Если вы оптимизируете для малых xy и больших ab:

Создайте массив с наименьшим общим кратным из всех x, x+1, x+2... y. Например, для 2, 3, 4, 5 будет 60, а не 120.

Теперь заполните этот массив логическими значениями - сначала false для каждой ячейки, затем для каждого числа в x-y заполните все записи в массиве, кратные этому числу, значением true.

Теперь для каждого числа в a-b индексируйте массив по модулю длины массива, и если это правда, пропустите, если оно ложно, вернитесь.

Вы можете сделать это немного быстрее, удалив из ваших чисел с множителями от x до y, разложения простых множителей которых являются строгими надмножествами разложений простых множителей других чисел. Я имею в виду, что если у вас есть 2, 3, 4, 5, 4, это 2 * 2 строгое надмножество 2, поэтому вы можете удалить его, и теперь длина нашего массива составляет всего 30. Для чего-то вроде 3, 4, 5, 6 однако 4 равно 2*2, а 6 равно 3*2. 6 является надмножеством 3, поэтому мы удаляем его, но 4 не является надмножеством всего, поэтому оставляем его. НОК равно 3*2*2*5 = 60. Выполнение такого рода вещей само по себе дало бы некоторое ускорение для больших ab, и вам может не понадобиться идти в направлении массива, если это все, что вам нужно.

Кроме того, имейте в виду, что если вы не собираетесь использовать весь результат функции каждый раз — например, иногда вас интересует только наименьшее значение — напишите его как генератор, а не как функцию. Таким образом, вы можете звонить до тех пор, пока у вас не будет достаточно номеров, а затем остановиться, сэкономив время.