Я реализую Сито Эратосфена, для объяснения этого см. http://en.wikipedia.org/wiki/Сито_Эратосфена. Однако я хотел бы адаптировать его для генерации M простых чисел, а не простых чисел от 1 до N. Мой метод сделать это состоит в том, чтобы просто создать достаточно большое N, чтобы все M простых чисел содержались в этом диапазоне. Есть ли у кого-нибудь хорошие эвристики для моделирования роста простых чисел? Если вы хотите опубликовать фрагменты кода, я реализую это на Java и C++.
Алгоритмы динамического сита для простого поколения
comment
существует версия алгоритма сита, которую вы можете реализовать с двумя массивами, каждый из которых имеет размер, равный количеству простых чисел, которые вы хотите найти. Один содержит простые числа, другой содержит простое число, кратное простому числу с тем же индексом. Таким образом, вам не нужно вычислять размер сита (N в вашем вопросе).
- person hatchet - done with SOverflow schedule 26.09.2011
Ответы (5)
Чтобы сгенерировать M простых чисел, вам нужно подняться примерно до M log M. См. Приближения для n-го простого числа в этой статье Википедии о теореме о простых числах. Чтобы быть в безопасности, вы можете захотеть переоценить - скажем, N = M (log M + 1).
Отредактировано для добавления: Как отмечает Дэвид Хаммен, это завышение не всегда достаточно хорошо. Статья в Википедии дает M (log M + log log M) в качестве безопасной верхней границы для M >= 6.
person
TonyK
schedule
26.09.2011
Относительно Чтобы быть в безопасности, вы можете захотеть переоценить - скажем, N=M(log M + 1) - это недостаточно консервативно. Пример: 1619-е простое число равно 13693, но ваше выражение дает только 13582,7. Статья в вики дает верхнюю границу, действительную для всех M > 5, N = M log (M log M)
- person David Hammen; 26.09.2011
@David: Спасибо, что указали на это! Я отредактировал свой ответ. Но я не вижу вашего выражения M log (M log M) в связанной статье.
- person TonyK; 26.09.2011
M log (M log M) = M log M + M log log M. Это следует непосредственно из log (AB) = log A + log B и дистрибутивности умножения над сложением. Я не знаю, почему в вики-статье использовалась гораздо более подробная правая часть идентификатора.
- person David Hammen; 26.09.2011
Если вы не доверяете моей математике, доверьтесь Wolfram Alpha: wolframalpha.com/input/ . Прокрутите вниз до Альтернативная форма, предполагающая положительное значение M:.
- person David Hammen; 26.09.2011
@David: Единственная причина, по которой я не ответил на твой предыдущий комментарий, это то, что я был слишком смущен. Ваша логика, конечно, безупречна.
- person TonyK; 27.09.2011
также обсуждается здесь: stackoverflow.com /вопросы/1042902/
- person hatchet - done with SOverflow; 27.09.2011
Это приближение n-го простого числа взято из Википедии; поэтому вам просто нужно выделить массив m*log(m)+m*log(log(m)); массива m*log(m) будет недостаточно.
person
Simone
schedule
26.09.2011
Другой альтернативой является сегментированное сито. Просеять числа до миллиона. Потом второй миллион. Потом третий. И так далее. Остановитесь, когда у вас будет достаточно.
Нетрудно сбросить сито для следующего сегмента. Подробнее см. в моем блоге.
person
user448810
schedule
26.09.2011
Почему бы не увеличить сито динамически? Всякий раз, когда вам нужно больше простых чисел, перераспределите память seive и запустите алгоритм sieve прямо над новым пространством, используя простые числа, которые вы ранее нашли.
person
Robᵩ
schedule
26.09.2011
Кроме того, это нарушило бы суть сита, мне пришлось бы повторять каждое из ранее обнаруженных простых чисел каждый раз, когда я увеличивал сито, что резко замедляло мою программу.
- person Daniel Gratzer; 27.09.2011
правильно, это то, что известно сегментированное сито, я думаю. Только одно уточнение, вы, конечно, не начинаете заново с самого начала, а просеиваете постоянно увеличивающиеся промежутки между последовательными квадратами простых чисел с каждым новым простым числом (поэтому нет необходимости ** пере-** распределять). Когда не хватает памяти и вы начинаете использовать более короткий массив просеивания, @jozefg только тогда производительность начнет страдать.
- person Will Ness; 28.01.2012
На ум приходят ленивые вычисления (например, Haskell и другие функциональные языки делают это за вас). Хотя вы пишете на императивном языке, я думаю, вы можете применить эту концепцию.
Рассмотрим операцию удаления оставшихся количественных чисел из набора кандидатов. Фактически, не касаясь реального алгоритма (и, что более важно, не угадывая, сколько чисел вы создадите), выполните эту операцию в ленивом режиме (которую вам придется реализовать, потому что вы говорите на императивном языке), когда и если вы попытаетесь взять наименьшее оставшееся число.
person
bitmask
schedule
26.09.2011
