Comments 28
Спасибо, читал с удовольствием.
+5
Было бы так же просто вычислять длинные простые числа (скажем, в районе 10³²), тогда пришлось бы срочно выдумывать что-нибудь новое в области защиты информации :)
0
Найти несколько последовательных простых такого порядка — не проблема. Например, следующее после 1032 — это 100000000000000000000000000000049. Но это вычисляют не методом решета, а индивидуальными тестами. Метод решета, скажем, при 1024 потребует несколько сотен гигабайт памяти.
+4
Вроде бы с этой задачей может справиться решето Сундарама.
0
Формально вы правы, решето Сундарама не требует предварительного построения таблицы простых до sqrt(n), так что на этом память можно сэкономить совершенно. Однако нам понадобится хранить в памяти просеиваемый интервал. Если он длиннее [n, n+sqrt(n)], то мы уже имеем потребление памяти порядка O(sqrt(n)) и без потери порядка асимптотики можем применить решето Эратосфена или Аткина. Если же он короче [n, n+sqrt(n)], то решето Сундарама по производительности проиграет даже поэлементной проверке перебором делителей.
0
Статья, во-первых, очень интересная и познавательная, а во-вторых, прекрасно оформленная. За это автору двойное спасибо.
+3
> Из элементарной теории чисел следует, что все простые, большие 3, имеют вид 12k+1 (случай a), 12k+5 (снова a), 12k+7 (случай b) или 12k+11 (случай c).
не понял, а как же 5, 7?
не понял, а как же 5, 7?
0
k = 0
+3
k >= 0.
5 и 7 получаются при k = 0.
5 и 7 получаются при k = 0.
+2
Кстати, а почему тогда не 6k+-1, k>0 — можно ещё в 1.5 раза уменьшить потребление памяти.
-2
Вы в логике ошиблись. Из того, что все простые, большие 3 имеют такой вид, вовсе не означает, что все числа, имеющие такой вид, простые.
Иначе, если из A следует B, это не значит, что из B следует B.
Если все крокодилы зелёные, это не значит, что все зелёные предметы — крокодилы.
Иначе, если из A следует B, это не значит, что из B следует B.
Если все крокодилы зелёные, это не значит, что все зелёные предметы — крокодилы.
0
Я в своё время писал курсач на тему «сравнения эффективности алгоритмов дискретного логарифмирования». Практическую часть делал на JS. Для работы с большими числами использовал библиотеку BigInt, для распараллеливания юзал Воркеров. Может быть кому-то интересен данный опыт, поэтому спрашивайте. Ну и с простыми числами знаком не по наслышке. Единственный известный детерминированный алгоритм тестов на простоту — это тест Агравала — Каяла — Саксены. Но я делал по-другому: для поиска очень крупных (сотни знаков) простых чисел, выбиралось случайное нечетное число и применялся алгоритм Миллера-Рабина много раз (используя теорему Рабина, вероятность получения псевдопростого числа можно снизить почти до нуля).
+2
Спасибо за статью.
Вроде бы, O(n^(1/2)) — это не экспоненциальный рост, а экспоненциальный — это O(a^n).
Вроде бы, O(n^(1/2)) — это не экспоненциальный рост, а экспоненциальный — это O(a^n).
+1
Он становиться экспотенциальным если мы учтем длинну числа, что актуально для больших простых, когда, например, сложение сложение 2 чисел занимает не О(1), как для чисел до 10^9 на привычных нам 32-хбитных системах, а О(длинна числа)
+1
N-ое простое число имеет порядок примерно n * ln n, значит его длина — ln n + ln ln n или примерно ln n (если верить статье и считать, что ln ln n это очень мало). Получается, алгоритм работает за O(ln n * n^(1/2)). А это тоже совсем не экспоненциально, и даже быстрее, чем линейно.
+1
Если взять машину Тьюринга, относительно к которой применяются и изучаются, все тесты сложности, то там число представляется как длина входных данных, а это длина битового слова. То есть n — это длина 2-го числа, само число же до 2^n.
Теорема P/NP тоже формулируется относительно машины Тьюринга.
P.S: ошибочность этого мнения происходит из того, что в повседневной жизни мы оцениваем сложение двух чисел как O(1), потому что они ограничены 2^32.
Теорема P/NP тоже формулируется относительно машины Тьюринга.
P.S: ошибочность этого мнения происходит из того, что в повседневной жизни мы оцениваем сложение двух чисел как O(1), потому что они ограничены 2^32.
0
Смотря относительно чего. Я в статье пишу, что O(n^(1/2)) — это величина, которая «растет экспоненциально относительно битовой длины n», т. е. относительно log_2 n. АФАИР это стандартный подход: сложность алгоритма измеряется относительно длины входных данных. Относительно самого n это, конечно, полиномиальный рост.
+1
Экспоненциальный относительно длины n, то есть относительно log n.
0
>JavaScript-подобный псевдокод
Раньше писали «C-подобный».
Раньше писали «C-подобный».
+4
Сразу вспомнились из теории чисел тесты Мюллера-Рабина и Соловея- Штрассена на проверку простоты числа. Надо бы и их тоже закодить.
0
Прекрасная статья. Спасибо!
+1
А зачем, позвольте спросить, обсчитывать все числа, если 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
0
В тексте статьи написано про wheel optimization.
0
Там происходит деление на 2, потом на 3, потом на 5, потом на 7. Чтобы не делить на 2 и 3 нужно разбить числа на ряды по 6 штук и выбросить 2,3,4 и 6-й ряды чтобы избежать математики. Лишь это хотел подчеркнуть, про оптимизацию то написано, а как она устроена ни слова.
0
Sign up to leave a comment.
Еще раз о поиске простых чисел