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

Одна из таких распространенных математических проблем - это способность находить простые числа. Я принял вызов и реализовал оптимизированное сито эратосфенов, предположив, что число 2 является простым, и уменьшил вдвое требуемое пространство памяти, как и многие другие. Согласно тестам, мое решение было второй самой быстрой реализацией среди всех участников, но и первое, и второе самые быстрые решения были по существу одинаковыми. Но пока тестировались решения участников, я обнаружил очень дискретный шаблон, который позволил мне предложить другое решение, которое было намного быстрее, чем любое решение, представленное в задаче. Я по-прежнему занял второе место, потому что испытатель «владелец» (и победитель испытания) не хотел тестировать мое новое решение.

Отказ от ответственности: я не математик. Я программист, который случайно наткнулся на это, участвуя в задаче, и продолжал исследовать до определенного момента.

Мое решение начинается с предположения, что все знают, что числа 2 и 3 являются простыми числами. Всем известно, что после цифры 2 простыми могут быть только нечетные числа. Но я пошел еще дальше, исключив все нечетные числа, кратные 3.

Список точек:

  • Кратное 3 либо нечетное, либо четное (спасибо Captain Obvious);
  • Даже числа, кратные 3, складываются путем умножения 2 и 3, поэтому они по существу кратны 6;
  • Нет других нечетных чисел, кроме тех, которые были до и после 6, которые не были бы кратны 3 (потому что вокруг нечетных чисел, кратных 3, вы найдете только четные числа, а с нечетными числами, которые находятся вокруг кратных 6, вы в основном охватываете все числа. возможный);

Делая это, вы эффективно сокращаете часть требований к памяти ... за исключением того, что на самом деле вы не можете знать, сколько слотов памяти нужно перепрыгнуть таким образом. Или можно?

Сито разделено на два столбца: один имеет размер 6 * n-1, а другой - 6 * n + 1. Удалим из столбцов все числа, кратные 5:

Вы видите закономерность? Его можно выразить как 6 * (5 * n + 1) -1 и 6 * (5 * n – 1) +1. Попробуем проделать то же самое с числом 7:

Обратите внимание, что формулы стали перевернутыми. В этом случае мы должны выразить это как 6 * (7 * n + 1) +1 и 6 * (7 * n – 1) -1. И картина становится более запутанной, когда мы переходим ко второй строке простых чисел:

Это сокращает расстояние между непростыми числами одного и того же простого числа в столбцах. Теперь формулы для 11 равны 6 * (11 * n + 2) -1 и 6 * (11 * n – 2) +1, а для 13 - 6 * (13 * n + 2) +1 и 6 * (13 * n – 2) -1.

Но закономерность все же есть. Если вы продолжите делать это для следующего набора чисел, вы заметите, что значение, которое изменяется, увеличивается каждый раз, когда мы перемещаем одну строку. Например: формулы для 17 и 19: 6 * (17 * n + 3) -1, 6 * (17 * n – 3) +1 и 6 * (19 * n + 3) +1, 6 * (19 * n – 3) -1 соответственно. Итак, изменение между этими формулами зависит от другой переменной: индекса числа в столбце.

Зная это, становится легко реализовать сито, которое работает так же, как существующие сита. Но мы все еще можем упростить эти формулы. Давайте назовем pc1 и pc2 переменные, которые соответствуют простым числам в столбцах 1 и 2 соответственно, и i индекс (не отсчитываемый от нуля) где мы можем найти простое число. Из того, что мы знаем ранее, вот что у нас есть:

6*(pc1*n+i)-1, 6*(pc1*n-i)*n+1

6*(pc2*n+i)+1, 6*(pc2*n-i)-1

Значение i на самом деле может быть вычислено путем простого деления на 6 до ближайшего кратного 6 к простому числу (потому что это n-е кратное 6, которое эта система на основе), что означает, что соответственно для каждого столбца:

i = (pc1+1)/6

i = (pc2–1)/6

So:

6*(pc1*n+(pc1+1)/6)-1, 6*(pc1*n-(pc1+1)/6)+1

6*(pc2*n+(pc2-1)/6)+1, 6*(pc2*n-(pc2–1)/6)-1

И потому, что мы всегда должны упрощать наши формулы:

6*pc1*n+pc1, 6*pc1*n-pc1

6*pc2*n+pc2, 6*pc2*n-pc2

Итак, обратите внимание, что теперь у нас есть одинаковые точные формулы для обоих столбцов, а это означает, что мы должны отказаться от номенклатуры pc1 и pc2 с помощью чего-то более общего, например p :

6*p*n+p, 6*p*n-p

У нас все еще есть две формулы, одна для столбца, соответствующего простому числу, а другая для противоположного (соответственно), что достаточно, чтобы упростить реализацию сита, но математически говоря, обе формулы могут быть объединены в одну формулу, которая дает два результата:

6*p*n±p

Каким бы ни было простое число p, эта формула всегда будет предоставлять два непростых числа (для каждой итерации n) рядом с кратными 6, где p - один из его факторов.

Используя эту стратегию, можно не только уменьшить потребность в памяти на 2/3 по сравнению с обычным ситом, но также сэкономить много циклов и операций чтения и записи в память.

Вы можете найти мою реализацию этого сита @ https://github.com/KTachyon/FastPrimeSieve

Репо содержит проект XCode, но вам просто нужно скомпилировать файл main.m, чтобы запустить его. На моей машине он рассчитал решето для первого миллиарда чисел чуть менее чем за 4 секунды.