Комментарии 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 будут выполняться ненужное число раз.
Писал своего Эратосфена году эдак в 2002.
На машине было то ли 128, то ли 256 мб памяти (не помню точно, до апгрейда это всё происходило или после), а хотелось проверять 4 миллиарда чисел — ну то есть максимум, что в int32 влезает.
Я поступил просто: флажок для каждого нечетного числа соответствовал одному биту, четные пропускались вообще. 4 млрд чисел / 16 = 256 мб памяти.
Внутри цикла индекс преобразовывался в битовую маску, проставлялись флажки тоже битовыми операциями.
Писалось всё на C++.
Время работы, если склероз не подводит, было что-то в районе 5 минут на Celeron-667.
Код за давностью лет, к сожалению, утерян.
На машине было то ли 128, то ли 256 мб памяти (не помню точно, до апгрейда это всё происходило или после), а хотелось проверять 4 миллиарда чисел — ну то есть максимум, что в int32 влезает.
Я поступил просто: флажок для каждого нечетного числа соответствовал одному биту, четные пропускались вообще. 4 млрд чисел / 16 = 256 мб памяти.
Внутри цикла индекс преобразовывался в битовую маску, проставлялись флажки тоже битовыми операциями.
Писалось всё на C++.
Время работы, если склероз не подводит, было что-то в районе 5 минут на Celeron-667.
Код за давностью лет, к сожалению, утерян.
Как по мне, в оптимальной реализации решето Эратосфена есть только одна хитрость, связанная с уменьшением количества проходов по последовательности чисел:
пусть N — максимальное число, то для вычеркивания чисел из последовательности нужно рассматривать все числа от 2 до sqrt(N). Для всех оставшихся чисел, больших sqrt(N), все непростые числа к этому моменту будут вычеркнуты. Естественно четные числа нужно пропускать.
N = 12
sqrt(12) = 3
После вычеркивания из последовательности всех чисел кратных двум и трем останутся только простые.Останется только по битовым маскам пройти, чтоб вывести невычеркнутые числа.
пусть N — максимальное число, то для вычеркивания чисел из последовательности нужно рассматривать все числа от 2 до sqrt(N). Для всех оставшихся чисел, больших sqrt(N), все непростые числа к этому моменту будут вычеркнуты. Естественно четные числа нужно пропускать.
N = 12
sqrt(12) = 3
После вычеркивания из последовательности всех чисел кратных двум и трем останутся только простые.Останется только по битовым маскам пройти, чтоб вывести невычеркнутые числа.
Если я правильно оцениваю объем памяти ln(n) — число найденных простых.
Неправильно. Количество простых чисел асимптотически растет как n/ln(n). Вы б сами себя проверили, ln (1000) всего лишь 7.
Ну и да, выходит что ваш алгоритм работает за prime_count^2 или я что-то упускаю? Какое это тогда решето Эратосфена?
Да. Вы правы. По памяти n/ln(n),
Но насчет 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());
}
то сложность поменьше будет. Хотя так сходу не могу прикинуть число. Буду думать.
Но насчет 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)) времени.
В Википедии написано гораздо лучше: Решето Эратосфена, Решето Аткина
Цель же не найти первых 1000 или 100 млн. Цель показать идею алгоритма.
Приведите пример задачи, где ваша идея будет лучше обычного решета с битовым массивом. Ваша идея даже памяти больше расходует — ~N / ln(N) * 2 * log2(N) = 2.885 * N бит против ~N бит.
Память можно экономить, выбирая только числа вида 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 и т.д.
Wheel factorization и т.п. по прежнему применимо при выборе следующего кандидата.
Прочитал, что это, да, действительно. Но я предлагаю так же и вычеркивать гораздо меньшее количество чисел. Только произведения простых чисел в определенном диапазоне. Но это так, разминка. Я хочу эти базы использовать для факторизации. Развернуть алгоритм в обратную сторону. Например, для числа меньшего 510510 делим его на 30030 и получаем остаток. Далее этот остаток делим на 2310, полученный остаток делим на 210, полученный остаток делим на 30 и получаем число, которое либо простое, либо нет. Если нет, то делитель находится среди чисел до 30. Если простое, то делитель может быть от 31 до 199, включая квадраты 11, 13 и произведение 11 на 13. Если и этот остаток простой, значит делитель может быть в диапазоне от 211 до 2299. Если и это число простое, то проверяем следующий диапазон от 2311 до 30030, количество пар примерно четверть от соответствующих чисел.
В целом это похоже на прохождение вдоль сегментов эллиптических кривых, до конца я этот момент еще не исследовал. Главный плюс в том, что мы сразу снижаем базу вычислений и количество операцний не корень из n, а корень из остатка от деления на ближайшую базу (просториал — простой факториал, произведение первых k простых чисел, не превышающее заданного числа)
В целом это похоже на прохождение вдоль сегментов эллиптических кривых, до конца я этот момент еще не исследовал. Главный плюс в том, что мы сразу снижаем базу вычислений и количество операцний не корень из 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*… для чисел, которые следует вычеркивать и количество этих чисел растет медленнее, чем количество вычисляемых простых чисел в соответствующей базе.
Меня же этот подход заинтересовал возможностью факторизации больших чисел понижением базы.
Если мы возьмем произведение двух больших простых чисел, мы можем быстро определить для него базу и остаток. Остаток резко понижает разрядность (до предыдущей базы, тут факториальная зависимость). При этом остаток уже содержит в себе наибольший из множителей.
Вот такая вот теорема.
В основе очень элементарная мысль. Каждое непростое число — это произведение простых. Каждое простое число — это сумма такого произведения и одного простого числа.
Таким образом, предыдущие простые числа однозначно определяют следующие числа. Необходимо же вычеркивать лишь произведения простых чисел. Первое просто число — 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*… для чисел, которые следует вычеркивать и количество этих чисел растет медленнее, чем количество вычисляемых простых чисел в соответствующей базе.
Меня же этот подход заинтересовал возможностью факторизации больших чисел понижением базы.
Если мы возьмем произведение двух больших простых чисел, мы можем быстро определить для него базу и остаток. Остаток резко понижает разрядность (до предыдущей базы, тут факториальная зависимость). При этом остаток уже содержит в себе наибольший из множителей.
Вот такая вот теорема.
Но, увы, легко найти контрпример. Например, 29*211=6119. Делим на 2310, получаем остаток 1499 — простое число. И необходимо для поиска все равно перебирать произведения простых чисел (и, единиц, начиная с третьего сомножителя) i*j*k*l*m*n*… в диапазоне от меньшего простого, не входящего в базу 2310, т.е. с 13 и до корня из 6119.
Для ещё доп оптимизации можно заменить код
на
т.к. меньшие непростые числа будут отсеяны предыдущими простыми числами
primes.add(new PrimePair(candidate, candidate));
на
primes.add(new PrimePair(candidate, candidate * candidate));
т.к. меньшие непростые числа будут отсеяны предыдущими простыми числами
1. Это не решето Эратосфена, а перебор делителей (trial division)
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. В решете Эратосфена без каких-либо ухищрений, используя банальнейший 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 разница становится еще более существенной.
1. Где же там делители? попыток деления не происходит.
2. Если надо искать тысячебитовые числа куда их складывать?
2. Если надо искать тысячебитовые числа куда их складывать?
Хм… извиняюсь, да, невнимателен был. Это не trial division, но и решетом Эратосфена это сложно назвать.
Но к памяти всё равно много вопросов.
В этом варианте на каждое простое используется пара простого и границы интервала. Размер такой структуры, конечно, зависит от реализации, но это никак не может быть меньше двух целых чисел. Если у вас целые всего 32 бита, то это 64 бита. Для того, чтобы это было выгодным по сравнению с BitSet (или подобной структурой), надо чтобы в среднем между простыми было 64 составных. А в целых этого диапазона примерно каждое 20-е простое.
С 1000-битными на самом деле для вашей модели не лучше. Количество требуемых бит для числа растет быстрее, чем средний интервал между простыми примерно в 1/ln(2) раз. Так что идея интересная, но не работает.
Ну и да, строить решето Эратосфена для 1000-битных чисел — нашей вселенной не хватит (ни места ни времени).
Если надо искать 1000-битные простые числа не в теории, а на практике, то в Java всё уже до нас придумано и почти всё сделано. У класса BigInteger есть метод probablePrime, а его уже можно проверить каким-либо из подходящих под задачу primality tests (в BigInteger только вероятностный, так что, увы — придётся писать).
Но к памяти всё равно много вопросов.
В этом варианте на каждое простое используется пара простого и границы интервала. Размер такой структуры, конечно, зависит от реализации, но это никак не может быть меньше двух целых чисел. Если у вас целые всего 32 бита, то это 64 бита. Для того, чтобы это было выгодным по сравнению с BitSet (или подобной структурой), надо чтобы в среднем между простыми было 64 составных. А в целых этого диапазона примерно каждое 20-е простое.
С 1000-битными на самом деле для вашей модели не лучше. Количество требуемых бит для числа растет быстрее, чем средний интервал между простыми примерно в 1/ln(2) раз. Так что идея интересная, но не работает.
Ну и да, строить решето Эратосфена для 1000-битных чисел — нашей вселенной не хватит (ни места ни времени).
Если надо искать 1000-битные простые числа не в теории, а на практике, то в Java всё уже до нас придумано и почти всё сделано. У класса BigInteger есть метод probablePrime, а его уже можно проверить каким-либо из подходящих под задачу primality tests (в BigInteger только вероятностный, так что, увы — придётся писать).
По памяти это, как уже правильно заметили в комментах, n / ln(n) — по факту мы держим количество простых и для каждого из них последнее зачеркнутое.
BigInteger может быть. java выбрана потому как для меня более знакомый язык. Корректнее бы на С писать выжимая все возможное побитово.
Вероятностный мало. Надо доказывать что это простое, а проверок будет слишком много.
В общем компьютер должен работать, а человек думать. Буду думать дальше. Спасибо за коммент.
BigInteger может быть. java выбрана потому как для меня более знакомый язык. Корректнее бы на С писать выжимая все возможное побитово.
Вероятностный мало. Надо доказывать что это простое, а проверок будет слишком много.
В общем компьютер должен работать, а человек думать. Буду думать дальше. Спасибо за коммент.
Чтобы уменьшить память надо использовать примитивы в PrimePair, как следствие не будет ещё и автобоксинга. Цикл лучше использовать через итератор и делать next и previous, вместо get(i)
Я рассматривал как вариант хранить только исключения вида i*j*k*..., рекурсивно вычисляя сами числа грейдами и не сохраняя простые числа как-то иначе.
Как я уже писал (и мне ответили про 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/ но видимо открывал велосипед и получил немало критических замечаний.
Как я уже писал (и мне ответили про 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/ но видимо открывал велосипед и получил немало критических замечаний.
Выходит, что числа 1,2,3,5 определяют простые числа до 29 (ближайшее меньшее 30). Добавляя числа 7,11,13 получаем числа до 203 (ближайшее меньшее 210). Добавляя числа 17,19,23,29,31,37,41,43,47,53,59,61,67,71,73, 79,83,89,97,101,103,107,109,113,127,131,137,139,149 получаем простые числа до 2303 (ближайшее меньшее 2310). Примерно в 7 раз больше, чем хранится в памяти. Далее, добавляя около 200 чисел получаем простые числа до 30030. Еще около 2000 чисел определяют числа до 510510. И так далее.
дубль
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решето Эратосфена, попытка минимизировать память