Проверка общего кратного для данного набора интервалов и потенциальных общих кратных - PullRequest
Новая
       29

Проверка общего кратного для данного набора интервалов и потенциальных общих кратных

0 голосов
/ 10 июля 2020

Следующая ситуация: у меня есть набор чисел, назовем его setX , и набор интервалов, назовем его setRanges . Мне нужно проверить, есть ли у любого X из setX хотя бы один делитель во всех заданных интервалах setRanges . Иначе говоря, я хочу проверить, является ли любой X из setX общим кратным хотя бы одному числу в каждом диапазоне. Прямо сейчас мой код выглядит примерно так: 

setX // Set of all X
setRanges // Set of all ranges

hasDivisor( X, [a,b] ):
  for i = a to b:
    if ( X % i == 0 ):
      return i

  return 0

for ( X in setX ):
  found = true
  for ( [a,b] in setRanges ):
    if ( hasDivisor == 0 ):
      found = false
      break
  
  if ( found )
    return true

return false

Числа в setX находятся в диапазоне от нескольких тысяч до примерно 1e15. Размер setX примерно такой же (до ~ 1e14). Количество тестируемых интервалов (размер setRanges) значительно невелико (менее 100).

Есть ли более эффективный способ решить эту проблему?

...