Комментарии 41
while (p.lastCrossed < candidate) {
p.lastCrossed += p.prime;
}
if (p.lastCrossed == candidate) {
//restart
candidate+=2;
i=-1;
}
Чем он лучше такой банальной проверки?
if (candidate % p.prime == 0) {
candidate += 2;
i = -1;
}
Например, для простого p=65537 верхний код будет выполнен один раз на 65537/2 итераций, а проверка условия в нижнем — каждую итерацию, при отсутствии делимости на остальной список простых. Код написан, чтобы ещё и минимизировать количество делений, которые для больших p будут выполняться ненужное число раз.
На машине было то ли 128, то ли 256 мб памяти (не помню точно, до апгрейда это всё происходило или после), а хотелось проверять 4 миллиарда чисел — ну то есть максимум, что в int32 влезает.
Я поступил просто: флажок для каждого нечетного числа соответствовал одному биту, четные пропускались вообще. 4 млрд чисел / 16 = 256 мб памяти.
Внутри цикла индекс преобразовывался в битовую маску, проставлялись флажки тоже битовыми операциями.
Писалось всё на C++.
Время работы, если склероз не подводит, было что-то в районе 5 минут на Celeron-667.
Код за давностью лет, к сожалению, утерян.
пусть N — максимальное число, то для вычеркивания чисел из последовательности нужно рассматривать все числа от 2 до sqrt(N). Для всех оставшихся чисел, больших sqrt(N), все непростые числа к этому моменту будут вычеркнуты. Естественно четные числа нужно пропускать.
N = 12
sqrt(12) = 3
После вычеркивания из последовательности всех чисел кратных двум и трем останутся только простые.Останется только по битовым маскам пройти, чтоб вывести невычеркнутые числа.
Если я правильно оцениваю объем памяти ln(n) — число найденных простых.
Неправильно. Количество простых чисел асимптотически растет как n/ln(n). Вы б сами себя проверили, ln (1000) всего лишь 7.
Ну и да, выходит что ваш алгоритм работает за prime_count^2 или я что-то упускаю? Какое это тогда решето Эратосфена?
Но насчет prime_count^2 нет.
для 2 мы сделаем не более n/2 сложений, для 3 — n/3 и т.д.
получаем n/2 + n/3 + n/5… то есть n * log log(n)
а если 2 выкинуть четные незачем проверять. И вот чуть ниже есть коммент что стартовать можно с candidate^2 и перепрыгивать при суммировании
if (p.lastCrossed < candidate) {
p.lastCrossed += p.prime * Math.round((candidate — p.lastCrossed) / p.prime());
}
то сложность поменьше будет. Хотя так сходу не могу прикинуть число. Буду думать.
StanislavL
Мда… Попытка минимизировать память и алгоритм запускается для 1000…
Ваше "решето" использует N^(1+o(1)) памяти и N^(2+o(1)) времени.
В Википедии написано гораздо лучше: Решето Эратосфена, Решето Аткина
По операциям n log(log(n)) (n/2 + n/3 + n/5+… n/Pk… +)
Память можно экономить, выбирая только числа вида 6n+-1, далее 30n+-1,7,11,13, далее 210n+-1,11,13,17,19,23,29,… потом 2310n+-1,13,17,… и так постепено от 1/2 (нечетные) мы переходим к 1/3, 4/15 и т.д.
В целом это похоже на прохождение вдоль сегментов эллиптических кривых, до конца я этот момент еще не исследовал. Главный плюс в том, что мы сразу снижаем базу вычислений и количество операцний не корень из n, а корень из остатка от деления на ближайшую базу (просториал — простой факториал, произведение первых k простых чисел, не превышающее заданного числа)
Если подкините ссылок почитать могу присоединиться к группе «подумать над».
Спасибо.
В основе очень элементарная мысль. Каждое непростое число — это произведение простых. Каждое простое число — это сумма такого произведения и одного простого числа.
Таким образом, предыдущие простые числа однозначно определяют следующие числа. Необходимо же вычеркивать лишь произведения простых чисел. Первое просто число — 2. Если мы рассматриваем 2n+1, то получаем числа 3 и 5. Далее, 2*3 это 6 — новая база. 6n+1 и 6n+5 дают следующую порцию чисел 7, 11, 13, 17, 19, 23, 25 и 29. Но 25 непростое число. т.е. 6*4+1 оказывается равным 5*5. Это значит, что из сгенерированных чисел нужно вычеркивать числа вида i*j, каждое из которых должно быть больше входящих в базу (т.е. не 2 и не 3, начинаем с 5) и их произведение не должно быть больше следующей базы (т.е. 2*3*5). Это значит что первый множитель не больше корня квадратного из 30, второй не больше 30 деленного на наименьший множитель, т.е. на 5.
Далее переходим к числам 30n плюс один и полученные ранее простые числа, большие уже вошедших в базу (т.е. не 2, не 3 и не 5). Так мы получаем числа 31, 37, 41, 43 и так далее до 209. После чего мы должны вычеркнуть числа вида i*j*k, учитывая, что k может быть равно 1, i находится в диапазоне от 7 до корня квадратного из 210, j не более 30.
И так мы генерируем числа все дальше и дальше, по следующим базам 2*3*5*7*11*13*17*19*23*29*… каждый раз используя ограниченный список простых чисел из предыдущей базы, который не обязательно весь хранить в памяти, а можно вычислять рекурсивно, если памяти недостаточно. Можно использовать сегментное вычисление чисел из необходимого диапазона фрагментами, на который хватает памяти. По сути нужно вычислять лишь произведения i*j*k*l*m*n*o*p*… для чисел, которые следует вычеркивать и количество этих чисел растет медленнее, чем количество вычисляемых простых чисел в соответствующей базе.
Меня же этот подход заинтересовал возможностью факторизации больших чисел понижением базы.
Если мы возьмем произведение двух больших простых чисел, мы можем быстро определить для него базу и остаток. Остаток резко понижает разрядность (до предыдущей базы, тут факториальная зависимость). При этом остаток уже содержит в себе наибольший из множителей.
Вот такая вот теорема.
Закономерности некоторые наблюдаются… но чего-то не хватает. И как доказывать я увы…
primes.add(new PrimePair(candidate, candidate));
на
primes.add(new PrimePair(candidate, candidate * candidate));
т.к. меньшие непростые числа будут отсеяны предыдущими простыми числами
2. В решете Эратосфена без каких-либо ухищрений, используя банальнейший BitSet можно положить все положительные int 0..2^31-1 в 256 мегабайт. При этом в этом объёме примерно 105 млн простых (спасибо www.wolframalpha.com за подсказку). Т.е. при хранении в массиве это будет примерно 400 мегабайт (если хранить компактно).
3. Если из BitSet выкинуть даже биты, соответствующие составным числам в интервале 1..30 т. е. считать, что остались только 1, 7, 11, 13, 17, 19, 23, 29 по модулю 30, то это усложнит арифметику, но позволит все простые intы уместить в 70 МБ. При переходе в long разница становится еще более существенной.
2. Если надо искать тысячебитовые числа куда их складывать?
Но к памяти всё равно много вопросов.
В этом варианте на каждое простое используется пара простого и границы интервала. Размер такой структуры, конечно, зависит от реализации, но это никак не может быть меньше двух целых чисел. Если у вас целые всего 32 бита, то это 64 бита. Для того, чтобы это было выгодным по сравнению с BitSet (или подобной структурой), надо чтобы в среднем между простыми было 64 составных. А в целых этого диапазона примерно каждое 20-е простое.
С 1000-битными на самом деле для вашей модели не лучше. Количество требуемых бит для числа растет быстрее, чем средний интервал между простыми примерно в 1/ln(2) раз. Так что идея интересная, но не работает.
Ну и да, строить решето Эратосфена для 1000-битных чисел — нашей вселенной не хватит (ни места ни времени).
Если надо искать 1000-битные простые числа не в теории, а на практике, то в Java всё уже до нас придумано и почти всё сделано. У класса BigInteger есть метод probablePrime, а его уже можно проверить каким-либо из подходящих под задачу primality tests (в BigInteger только вероятностный, так что, увы — придётся писать).
BigInteger может быть. java выбрана потому как для меня более знакомый язык. Корректнее бы на С писать выжимая все возможное побитово.
Вероятностный мало. Надо доказывать что это простое, а проверок будет слишком много.
В общем компьютер должен работать, а человек думать. Буду думать дальше. Спасибо за коммент.
Чтобы уменьшить память надо использовать примитивы в PrimePair, как следствие не будет ещё и автобоксинга. Цикл лучше использовать через итератор и делать next и previous, вместо get(i)
Я знаю как ускорять java. Так написано чтобы было понятнее как работает алгоритм.
Как я уже писал (и мне ответили про wheel factirization, обязательно изучу, о чем это), можно развивать простые числа по принципу
2n+1 (дает числа 3 и 5),
6n+{1,5} (дает числа 7, 11, 13, 17, 19, 23, 25, 29} и нужно сохранить лишь одно число пока 5*5, как исключение.
30n+{1,7,11,13,17,19,23,29}, которое дает все простые числа до 209, плюс произведения i*j, где 7<=i,j<=sqrt(210)
Далее будет база 2*3*5*7=210 простых чисел до 2309 (2*3*5*7*11-1) и нужно исключать произведения i*j*k*… где 11<=i,j,k,..<=sqrt(2310)
Данная рекурсия может быть вообще чисто вычислительной, не используя память для хранения всех чисел (например при проверке числа на простоту), а для вычисления последовательных чисел можно заметить просто правило, 6n+{1,5} = 6m+-1, 30n+{1,7,11,13,17,19,23,29}= 30m+-{1,7,11,13} и т.д.то есть — зеркальная симметрия каждого такого блока. И блоки большего размера фрактально повторяются из блоков меньшего размера.
Я писал как-то статью на эту тему здесь https://habrahabr.ru/post/255527/ но видимо открывал велосипед и получил немало критических замечаний.
Решето Эратосфена, попытка минимизировать память