Поиск чисел от a до b, не делящихся на x на y

Question

Это проблема, о которой я долго размышлял.

Каков самый быстрый способ найти все числа от a до b, которые не делятся на любое число от x до y?

Рассмотрим это:

Я хочу, чтобы найти все числа от 1 до 10, которые не делятся на 2 до 5. Этот процесс будет крайне медленным, если я где использовать линейный подход; Как это:

result = [] 
a = 1 
b = 10 
x = 2 
y = 5 
for i in range(a,b): 
    t = False 
    for j in range(x,y): 
     if i%j==0: 
      t = True 
      break 
    if t is False: 
     result.append(i) 
return result 

Кто-нибудь знает о каких-либо других способов сделать это с меньшими затратами времени вычислений, чем линейное решение?

Если нет, может кто-нибудь увидеть, как это мощь сделать быстрее, так как я пустой в этот момент ...

С уважением, Джон

[EDIT]

Диапазон значений от 0 до> 1, e + 100

Это верно для a, b, x и y

Answer 1

Вам нужно всего лишь проверить основные значения в диапазоне возможных делителей - например, если значение не делится на 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 секунд.

Answer 2

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

Если вы оптимизации для малых х-у и большой а-б:

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

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

Теперь для каждого числа а-б, индекс в массиве по модулю arraylength и если это правда, пропустить еще, если оно ложно, возвращение.

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

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