Подскажите с реализацией решета эратосфена

Я бы хотел помимо четных чисел не рассматривать также числа, которые делятся на 3, 5 и т.д. Вот мой код для рассмотрения только нечетных чисел

def ProovedSieve(n):
    e, p = [2], (n + 1) // 2
    Bool = [True] * p
    Bool[0] = False
    for d in range(1, ceil((p / 2) ** 0.5)):
        if Bool[d]:
            q = 2 * d + 1
            Bool[2 * d * (d + 1)::q] = (p - 2 * d * d) // q * [False]
            Bool[d] = False
            e.append(q)
    return e + list(itertools.compress(range(1, n + 1, 2), Bool))

Такой код относительно быстр, работает для n = 10 ** 7 за 0.6 сек. Я пользуюсь формулой определения индекса q^2, где q - некоторое простое число, через индекс этого простого числа в массиве нечетных чисел(d)(Вывел самостоятельно). Список Bool - хранит нечетные числа от 1 до n. Подскажите есть ли подобные формулы для подобного определения минимального такого делителя t некоторого простого числа k, такого, что t>= k ^ 2 для каждого из списков: n элемент первого задается по формуле 6n + 1, второго - 6n + 5. Если такие есть - подскажите, если нет, то помогите вывести(Ps. Я перехожу в 9 класс и высшая математика, пределы, интегралы, кольца вычетов и т.д. мне неподвластны.


Ответы (0 шт):