Стандартное сито Эратосфена многократно вычеркивает большинство композитов; на самом деле единственные, которые не отмечены более одного раза, это те, которые являются произведением ровно двух простых чисел. Естественно, при увеличении размера сит увеличивается.

Для нечетного сита (то есть без четных чисел) переполнение достигает 100% для n = 3 509 227, с 1 503 868 композитами и 1 503 868 вычеркиваниями уже вычеркнутых чисел. Для n = 2 ^ 32 перерасход повышается до 134,25% (перерасход 2 610 022 328 против подсчета поп-музыки 1 944 203 427 = (2 ^ 32/2) - 203 280 221).

Сито Сундарама - с другим объяснением вmaths.org - может быть немного умнее, если - и только если - пределы цикла вычисляются разумно. Тем не менее, это то, что источники, которые я видел, выглядят как «оптимизация», и также кажется, что неоптимизированный Сундарам каждый раз избивается Эратосфеном, который имеет только шансы.

Интересно то, что оба создают абсолютно одинаковое окончательное растровое изображение, то есть то, где бит k соответствует числу (2 * k + 1). Таким образом, оба алгоритма должны в конечном итоге устанавливать одни и те же биты, у них просто разные способы решения этой задачи.

У кого-то есть практический опыт работы с конкурентоспособным, настроенным Сундарамом? Может ли это побить старый греческий?

Я уменьшил код для моего небольшого сито (2 ^ 32, греческий только для коэффициентов) и настроил размер сегмента до 256 КБ, что является оптимальным для старого Nehalem с его 256 КБ L2 и для более новых ЦП (даже хотя последние гораздо больше прощают большие сегменты). Но теперь я ударился о кирпичную стену, и кровавое сито все еще требует 8,5 с для инициализации. Загрузка сита с жесткого диска - не очень привлекательный вариант, а многопоточность трудно сделать переносимым способом (поскольку библиотеки, такие как boost, склонны переносить гаечный ключ в мобильность) ...

Может ли Sundaram сбрить несколько секунд с момента запуска?

P.S .: Перегрузка как таковая не является проблемой и будет поглощена кэшем L2. Дело в том, что стандартный Эратосфен, кажется, выполняет работу более чем в два раза, чем необходимо, что указывает на то, что может быть потенциал для выполнения меньшего количества работы быстрее.