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