Алгоритм удаления сита , упомянутый Бенгольдбергом , заслуживает более пристального внимания, не только потому, что он очень элегантный, но и потому, что иногда он может быть полезен на практике (в отличие от сита Аткина, которое является чисто академическим упражнения).
Основная идея, лежащая в основе алгоритма решетчатого сита, состоит в том, чтобы использовать небольшое скользящее сито, которое является достаточно большим, чтобы содержать хотя бы одно отдельное кратное число для каждого из «активных» простых множителей в настоящее время - то есть тех простых чисел, чье квадратное число не превышает наименьшее число в настоящее время представлено движущимся ситом. Другое отличие от SoE состоит в том, что сито deque сохраняет фактические факторы в ячейках композитов, а не логических значений.
Алгоритм расширяет размер окна сита по мере необходимости, что приводит к довольно равномерной производительности в широком диапазоне, пока сито не начнет заметно превышать емкость кэша L1 ЦП. Последнее простое число, которое подходит полностью, составляет 25 237 523 (1579 791-е простое число), что дает приблизительную приблизительную цифру для разумного рабочего диапазона алгоритма.
Алгоритм довольно прост и надежен, и его производительность даже в гораздо более широком диапазоне, чем у несегментированного сита Эратосфена. Последний работает намного быстрее, пока его сито полностью помещается в кэш, то есть до 2 ^ 16 для сита, рассчитанного только на шансы, с размерами в байтах. Затем его производительность падает все больше и больше, хотя он всегда остается значительно быстрее, чем deque, несмотря на помехи (по крайней мере, в скомпилированных языках, таких как C / C ++, Pascal или Java / C #).
Вот рендеринг алгоритма deque sieve в C #, потому что я нахожу этот язык - несмотря на многие его недостатки - гораздо более практичным для прототипирования алгоритмов и экспериментов, чем чрезвычайно громоздкий и педантичный C ++. (Sidenote: я использую бесплатную LINQPad , которая позволяет без проблем погружаться в настройку проектов, make-файлов, каталогов или еще много чего, и дает мне ту же степень интерактивности как приглашение Python).
C # не имеет явного типа deque, но обычный List<int> работает достаточно хорошо для демонстрации алгоритма.
Примечание: эта версия не использует deque для простых чисел, потому что просто не имеет смысла выталкивать sqrt (n) из n простых чисел. Что хорошего в том, чтобы удалить 100 простых чисел и оставить 9900? По крайней мере, таким образом все простые числа собраны в аккуратный вектор, готовый для дальнейшей обработки.
static List<int> deque_sieve (int n = 10000)
{
Trace.Assert(n >= 3);
var primes = new List<int>() { 2, 3 };
var sieve = new List<int>() { 0, 0, 0 };
for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
{
int base_factor = sieve[0];
if (base_factor != 0)
{
// the sieve base has a non-trivial factor - put that factor back into circulation
mark_next_unmarked_multiple(sieve, base_factor);
}
else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite
{
primes.Add(sieve_base);
if (primes.Count == n)
return primes;
}
else // sieve_base == current_prime_squared
{
// bring the current prime into circulation by injecting it into the sieve ...
mark_next_unmarked_multiple(sieve, primes[current_prime_index]);
// ... and elect a new current prime
current_prime_squared = square(primes[++current_prime_index]);
}
// slide the sieve one step forward
sieve.RemoveAt(0); sieve_base += 2;
}
}
Вот две вспомогательные функции:
static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
int i = prime, e = sieve.Count;
while (i < e && sieve[i] != 0)
i += prime;
for ( ; e <= i; ++e) // no List<>.Resize()...
sieve.Add(0);
sieve[i] = prime;
}
static int square (int n)
{
return n * n;
}
Вероятно, самый простой способ понять алгоритм - это представить его как специальное сегментированное сито Эратосфена с размером сегмента 1, сопровождаемое областью переполнения, где простые числа останавливаются, когда они пересекают конец сегмента. За исключением того, что одна ячейка сегмента (a.k.a. sieve[0]) уже была просеяна, когда мы до нее добрались, потому что она переехала, когда была частью области переполнения.
Число, представленное sieve[0], содержится в sieve_base, хотя sieve_front или window_base также могут быть хорошими именами, которые позволяют проводить параллели с кодом Бена или реализациями сегментированных / оконных сит.
Если sieve[0] содержит ненулевое значение, то это значение имеет коэффициент sieve_base, который, таким образом, может быть распознан как составной. Поскольку ячейка 0 кратна этому коэффициенту, легко вычислить ее следующий переход, который просто равен 0 плюс этот коэффициент. Если эта ячейка уже занята другим фактором, мы просто добавляем фактор снова и так далее, пока не найдем множитель фактора, где в данный момент нет другого фактора (расширяя сито при необходимости). Это также означает, что нет необходимости хранить текущие рабочие смещения различных простых чисел от одного сегмента к другому, как в обычном сегментированном сите. Всякий раз, когда мы находим коэффициент в sieve[0], его текущее рабочее смещение равно 0.
Текущее простое число вступает в игру следующим образом. Простое может стать текущим только после своего вхождения в поток (то есть, когда оно было обнаружено как простое, потому что не помечено каким-либо фактором), и оно будет оставаться текущим до того момента, когда sieve[0] достигнет своего квадрата. Все более низкие кратные этого простого числа должны были быть исключены из-за действий меньших простых чисел, как в обычном SoE. Но ни одно из меньших простых чисел не может оторваться от квадрата, поскольку единственным фактором квадрата является само простое число, и на данный момент он еще не находится в обращении. Это объясняет действия, предпринятые алгоритмом в случае sieve_base == current_prime_squared (что, кстати, подразумевает sieve[0] == 0).
Теперь случай sieve[0] == 0 && sieve_base < current_prime_squared легко объясним: это означает, что sieve_base не может быть кратным любому из простых чисел, меньших текущего простого числа, иначе он был бы помечен как составной. Я также не могу быть большим кратным текущего простого числа, поскольку его значение меньше квадрата текущего простого числа. Следовательно, это должно быть новое простое число.
Алгоритм, очевидно, основан на Сите Эратосфена, но, очевидно, он сильно отличается. Сито Эратосфена получает превосходную скорость благодаря простоте своих элементарных операций: одно добавление индекса и одно хранилище для каждого шага операции - это все, что он делает в течение длительных периодов времени.
Вот простое несегментированное сито эратосфена, которое я обычно использую для просеивания простых чисел фактора в пределах короткого диапазона, т.е. до 2 ^ 16. Для этого поста я изменил его для работы за пределами 2 ^ 16, заменив int на ushort
static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
}
При просеивании первых 10000 простых чисел будет превышен типичный кэш L1 объемом 32 КиБайта, но функция все еще очень быстра (доля миллисекунды даже в C #).
Если вы сравните этот код с ситом deque, то легко заметить, что операции сита deque намного сложнее, и он не может эффективно амортизировать свои накладные расходы, потому что он всегда делает кратчайшие возможные отрезки подряд (ровно одно вычеркивание после пропуска всех уже вычеркнутых кратных значений).
Примечание: код C # использует int вместо uint, потому что новые компиляторы имеют привычку генерировать некачественный код для uint, вероятно, для того, чтобы подтолкнуть людей к целым числам со знаком ... В версии C ++ код выше я использовал unsigned везде, естественно; эталонный тест должен был быть в C ++, потому что я хотел, чтобы он базировался на предположительно адекватном типе deque (std::deque<unsigned>; при использовании unsigned short не было никакого увеличения производительности). Вот цифры для моего ноутбука Haswell (VC ++ 2015 / x64):
deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms
Примечание: время C # почти в два раза больше времени C ++, что довольно хорошо для C #, и это показывает, что List<int> не является дураком, даже если его используют как деку.
Простой ситовый код по-прежнему уносит ветвь из воды, даже если он уже работает за пределами своего нормального рабочего диапазона (размер кэш-памяти L1 превышен на 50%, при этом происходит перегрузка кеша). Доминирующая часть здесь - это чтение просеянных простых чисел, и это не сильно влияет на проблему с кешем. В любом случае функция была разработана для просеивания факторов факторов, то есть уровня 0 в трехуровневой иерархии сит, и обычно она должна возвращать только несколько сотен факторов или небольшое количество тысяч. Отсюда и его простота.
Производительность может быть улучшена более чем на порядок при использовании сегментированного сита и оптимизации кода для извлечения просеянных простых чисел (пошаговый мод 3 и развернутый дважды, или мод 15 и развернутый один раз), и все же можно повысить производительность. вне кода, используя колесо мод 16 или мод 30 со всеми обрезками (то есть полное развертывание для всех остатков). Нечто подобное объясняется в моем ответе на Найдите простое простое число в Code Review, где обсуждалась аналогичная проблема. Но трудно понять смысл улучшения времени за миллисекунды для одноразовой задачи ...
Для краткости рассмотрим следующие моменты времени C ++ для просеивания до 100 000 000:
deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms
В отличие от этого, сегментированное сито в C # с несколькими наворотами выполняет ту же самую работу за 95 мс (нет доступных временных интервалов C ++, поскольку в настоящее время я выполняю вызовы кода только в C #).
В интерпретируемом языке, таком как Python, все может выглядеть совершенно иначе ops (умножение и, возможно, даже деление). Это неизбежно подорвет преимущество простоты Решета Эратосфена, и это может сделать решение для настила немного более привлекательным.
Кроме того, во многих случаях, сообщаемых другими респондентами в этой теме, вероятно, преобладает время вывода . Это совершенно другая война, где моим основным оружием является простой класс, подобный этому:
class CCWriter
{
const int SPACE_RESERVE = 11; // UInt31 + '\n'
public static System.IO.Stream BaseStream;
static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range
static int m_write_pos = 0;
public static long BytesWritten = 0; // for statistics
internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();
internal static ushort[] create_double_digit_lookup ()
{
var lookup = new ushort[100];
for (int lo = 0; lo < 10; ++lo)
for (int hi = 0; hi < 10; ++hi)
lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);
return lookup;
}
public static void Flush ()
{
if (BaseStream != null && m_write_pos > 0)
BaseStream.Write(m_buffer, 0, m_write_pos);
BytesWritten += m_write_pos;
m_write_pos = 0;
}
public static void WriteLine ()
{
if (m_buffer.Length - m_write_pos < 1)
Flush();
m_buffer[m_write_pos++] = (byte)'\n';
}
public static void WriteLinesSorted (int[] values, int count)
{
int digits = 1, max_value = 9;
for (int i = 0; i < count; ++i)
{
int x = values[i];
if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
Flush();
while (x > max_value)
if (++digits < 10)
max_value = max_value * 10 + 9;
else
max_value = int.MaxValue;
int n = x, p = m_write_pos + digits, e = p + 1;
m_buffer[p] = (byte)'\n';
while (n >= 10)
{
int q = n / 100, w = m_double_digit_lookup[n - q * 100];
n = q;
m_buffer[--p] = (byte)w;
m_buffer[--p] = (byte)(w >> 8);
}
if (n != 0 || x == 0)
m_buffer[--p] = (byte)((byte)'0' + n);
m_write_pos = e;
}
}
}
Для записи 10000 (отсортированных) чисел требуется менее 1 мс. Это статический класс, потому что он предназначен для текстового включения в заявки на кодирование, с минимумом суеты и нулевых накладных расходов.
В общем, я обнаружил, что он будет на намного быстрее, если сфокусированная работа будет выполнена для целых пакетов, что означает просеивание определенного диапазона, затем извлечение всех простых чисел в вектор / массив, а затем уничтожение всего массива, затем просеять следующий диапазон и так далее, вместо того, чтобы смешивать все вместе. Наличие отдельных функций, ориентированных на конкретные задачи, также облегчает их смешивание и сопоставление, позволяет повторно использовать и облегчает разработку / тестирование.