Комментарии 28
Спасибо, читал с удовольствием.
Было бы так же просто вычислять длинные простые числа (скажем, в районе 10³²), тогда пришлось бы срочно выдумывать что-нибудь новое в области защиты информации :)
Найти несколько последовательных простых такого порядка — не проблема. Например, следующее после 1032 — это 100000000000000000000000000000049. Но это вычисляют не методом решета, а индивидуальными тестами. Метод решета, скажем, при 1024 потребует несколько сотен гигабайт памяти.
Вроде бы с этой задачей может справиться решето Сундарама.
Формально вы правы, решето Сундарама не требует предварительного построения таблицы простых до sqrt(n), так что на этом память можно сэкономить совершенно. Однако нам понадобится хранить в памяти просеиваемый интервал. Если он длиннее [n, n+sqrt(n)], то мы уже имеем потребление памяти порядка O(sqrt(n)) и без потери порядка асимптотики можем применить решето Эратосфена или Аткина. Если же он короче [n, n+sqrt(n)], то решето Сундарама по производительности проиграет даже поэлементной проверке перебором делителей.
Статья, во-первых, очень интересная и познавательная, а во-вторых, прекрасно оформленная. За это автору двойное спасибо.
> Из элементарной теории чисел следует, что все простые, большие 3, имеют вид 12k+1 (случай a), 12k+5 (снова a), 12k+7 (случай b) или 12k+11 (случай c).
не понял, а как же 5, 7?
не понял, а как же 5, 7?
k = 0
k >= 0.
5 и 7 получаются при k = 0.
5 и 7 получаются при k = 0.
Кстати, а почему тогда не 6k+-1, k>0 — можно ещё в 1.5 раза уменьшить потребление памяти.
Вы в логике ошиблись. Из того, что все простые, большие 3 имеют такой вид, вовсе не означает, что все числа, имеющие такой вид, простые.
Иначе, если из A следует B, это не значит, что из B следует B.
Если все крокодилы зелёные, это не значит, что все зелёные предметы — крокодилы.
Иначе, если из A следует B, это не значит, что из B следует B.
Если все крокодилы зелёные, это не значит, что все зелёные предметы — крокодилы.
Я в своё время писал курсач на тему «сравнения эффективности алгоритмов дискретного логарифмирования». Практическую часть делал на JS. Для работы с большими числами использовал библиотеку BigInt, для распараллеливания юзал Воркеров. Может быть кому-то интересен данный опыт, поэтому спрашивайте. Ну и с простыми числами знаком не по наслышке. Единственный известный детерминированный алгоритм тестов на простоту — это тест Агравала — Каяла — Саксены. Но я делал по-другому: для поиска очень крупных (сотни знаков) простых чисел, выбиралось случайное нечетное число и применялся алгоритм Миллера-Рабина много раз (используя теорему Рабина, вероятность получения псевдопростого числа можно снизить почти до нуля).
Спасибо за статью.
Вроде бы, O(n^(1/2)) — это не экспоненциальный рост, а экспоненциальный — это O(a^n).
Вроде бы, O(n^(1/2)) — это не экспоненциальный рост, а экспоненциальный — это O(a^n).
Он становиться экспотенциальным если мы учтем длинну числа, что актуально для больших простых, когда, например, сложение сложение 2 чисел занимает не О(1), как для чисел до 10^9 на привычных нам 32-хбитных системах, а О(длинна числа)
N-ое простое число имеет порядок примерно n * ln n, значит его длина — ln n + ln ln n или примерно ln n (если верить статье и считать, что ln ln n это очень мало). Получается, алгоритм работает за O(ln n * n^(1/2)). А это тоже совсем не экспоненциально, и даже быстрее, чем линейно.
Если взять машину Тьюринга, относительно к которой применяются и изучаются, все тесты сложности, то там число представляется как длина входных данных, а это длина битового слова. То есть n — это длина 2-го числа, само число же до 2^n.
Теорема P/NP тоже формулируется относительно машины Тьюринга.
P.S: ошибочность этого мнения происходит из того, что в повседневной жизни мы оцениваем сложение двух чисел как O(1), потому что они ограничены 2^32.
Теорема P/NP тоже формулируется относительно машины Тьюринга.
P.S: ошибочность этого мнения происходит из того, что в повседневной жизни мы оцениваем сложение двух чисел как O(1), потому что они ограничены 2^32.
Смотря относительно чего. Я в статье пишу, что O(n^(1/2)) — это величина, которая «растет экспоненциально относительно битовой длины n», т. е. относительно log_2 n. АФАИР это стандартный подход: сложность алгоритма измеряется относительно длины входных данных. Относительно самого n это, конечно, полиномиальный рост.
Экспоненциальный относительно длины n, то есть относительно log n.
>JavaScript-подобный псевдокод
Раньше писали «C-подобный».
Раньше писали «C-подобный».
Сразу вспомнились из теории чисел тесты Мюллера-Рабина и Соловея- Штрассена на проверку простоты числа. Надо бы и их тоже закодить.
Прекрасная статья. Спасибо!
А зачем, позвольте спросить, обсчитывать все числа, если 2/3 математического ряда вообще не участвуют в списке претендентов на простые числа?
$list = array();
for ($row = 1, $start = 1, $finish = 1000000; $start < $finish; $start++)
{
if ($row == 1 || $row == 5)
{
if (substr($start, -1) != 5)
{
$list[] = $start;
}
}
$row++;
if ($start % 6 == 0) $row = 1;
}
// echo count($list); // 266 666
В тексте статьи написано про wheel optimization.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Еще раз о поиске простых чисел