Алгоритмы динамического сита для первичной генерации

Question

Я реализую Сито Эратосфена, объяснение этого см. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. Однако я хотел бы адаптировать его для генерации M простых чисел, а не простых чисел от 1 до N. Мой способ сделать это просто создать достаточно большой N, чтобы все M простых чисел содержались в этом диапазоне. У кого-нибудь есть хорошая эвристика для моделирования роста простых чисел? Если вы хотите опубликовать фрагменты кода, я реализую это на Java и C ++.

Answer 1

Чтобы сгенерировать M простых чисел, вам нужно примерно до M log M. См. Аппроксимации для n-го простого числа в этой статье Википедии о теореме простых чисел. Чтобы быть в безопасности, вы можете переоценить - скажем, N = M (log M + 1).

Отредактировано, чтобы добавить: Как указывает Дэвид Хаммен, эта переоценка не всегда достаточно хороша. Статья Википедии дает M (log M + log log M) в качестве безопасной верхней границы для M> = 6.

Answer 2

Это приближение n-го простого числа взято из Википедии;поэтому вам просто нужно выделить массив m*log(m)+m*log(log(m));массив m*log(m) будет недостаточным.

Answer 3

Другой альтернативой является сегментированное сито. Просеять числа до миллиона. Тогда второй миллион. Потом третий. И так далее. Остановитесь, когда у вас будет достаточно.

Нетрудно сбросить сито для следующего сегмента. См. Мой блог для деталей.

Answer 4

На ум приходит ленивая оценка (например, Haskell и другие функциональные языки делают это за вас).Хотя вы пишете на императивном языке, вы можете применить концепцию, которую я думаю.

Рассмотрим операцию удаления оставшихся кардинальных чисел из набора кандидатов.Не касаясь реального алгоритма (и, что более важно, не угадывая сколько чисел вы создадите), выполните эту операцию ленивым образом (который вам придется реализовать, потому что вы 'на обязательном языке), когда и если вы попытаетесь взять наименьшее оставшееся число.

Answer 5

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