Возможно ли иметь Сито Эратосфена , которое сегментировано и использует факторизацию колес? Под факторизацией колеса Я имею в виду, например, пропускает кратные 2 и 3? По существу, сегментированное сито будет работать следующим образом:
- пусть max будет числом, от которого вы будете sh до go до
- получить все простые числа до квадрата root макс. с помощью простого сита
- в сегментах набирайте кратные этих простых чисел, начиная с первого кратного числа и прибавляя до конца сегмента
Пример:
- Пусть max = 100
- Тогда простые числа меньше, чем sqrt (100) = 2, 3, 5, 7
- Пусть размер сегмента будет 10
- первый сегмент после sqrt (100) будет [11, 20]
- Обычно go "11 не делится ни на один, поэтому он прост", "12 делится на 2, так что продолжайте добавлять от 2 до 12 до 20 "и т. Д. c.
- Но есть ли лучший способ пропустить кратные или 2 или 3 естественно?
Но как можно оптимизировать, пропуская известные композиты? В общем, я понимаю Sieve of Eratosthenes и факторизацию колес, но не понимаю, как их объединить. Имеет ли смысл использовать колеса с учетом того, что вы уже знаете все простые числа, на которые будут делиться композиты?