Обращение функции в сите Eratosthenes

Question

Я думаю, что это технически факторизация колес. Я пытаюсь повторно сжать представление моей программы "Сито Эратосфена", которое содержит только индексы чисел, которые, возможно, являются простыми.

Немного предыстории:

Основным колесом является [2]: отслеживайте 2 как первое простое число, а сито содержит только нечетные индексы. (50%))

Следующее колесо - [2 3]: следите за двумя и тремя в качестве первых простых чисел, а сито содержит только промежутки между 2*3=6 (то есть 1 и 5). Индексы имеют вид 6k+1 и 6k+5. (33%)

Следующее колесо - [2 3 5]: следите за 2, 3 и 5 как первыми простыми числами, и сите нужно только 8 бит для представления интервалов размера 30. (27%)

При очистке битов для кратных числа, я нахожу эти кратные, используя этот цикл:

def multiplesIndices (self, i):
    for gap in self.gaps[1:]:
        ret = i * (self.product * 0 + gap)
        if ret > len (self): break
            yield ret
    for k in xrange (1, len (self) / i / self.product + 1):
        for gap in self.gaps:
            ret = i * (self.product * k + gap)
            if ret > len (self): break
            yield ret

Проблема заключается во времени, необходимом для настройки колеса, в сочетании с уменьшением отдачи от степени сжатия. Что ж, и изменение rn на другой размер колеса требует много пересчета. Кроме того, изменяя размер колеса, я думаю, что могу повлиять на асимптотическую сложность.

Поэтому мое предлагаемое решение состоит в том, чтобы использовать маленькие колеса для инициализации больших колес: [2 3] (6/2), чтобы получить зазоры в колесе [2 3 5] (30/8) [2 3 5], чтобы получить зазоры в колесо [2 3 5 7] (210/48)

Там, где мне нужна помощь, это отображение уже вычисленного небольшого сита на предполагаемое вычисляемое большее сито, чтобы я мог избежать повторного просеивания всего от 1. Получите первые 30 простых чисел, используйте их, чтобы найти следующие 210-30 простых чисел, используйте их, чтобы найти следующие 480-210 простых чисел.

Более конкретно, мне нужна помощь для инвертирования этой функции (или правильной реализации invIndexOf()):

def indexOf (self, n):
    if not self.isValidIndex (n): raise Exception ()
    ret = n / self.product * len (self.gaps) + self.gaps.index (n % self.product)
    assert n in self.invIndexOf (ret)
    return ret

Кроме того, прошло несколько лет с тех пор, как я понял асимптотическую сложность чего-либо. Я уверен, что это улучшение, хотя и не радикальное.