simplecode 23 июн 2011 в 18:00

Алгоритм нахождения простых чисел

3 мин

501K

Алгоритмы *

Из песочницы

+28

Комментарии 64

TheShock 23 июн 2011 в 18:12

Сделайте листинг 7, в листинге 6 вынесите

int((sqrt(i)) + 1)

За пределы внутреннего цикла, т.к. вы впустую вызываете очень тяжёлую функцию корня. Другой вариант — это не вызывать тяжёлую функцию корня, а хранить ещё один массив из квадратов простых чисел, сравнивать размер с которым. Как-то так:

if (j * j - 1) > i:

Должно стать значительно быстрее.

simplecode 23 июн 2011 в 19:33

с замечаниями полностью согласен…

TheShock 23 июн 2011 в 19:48

Добавьте седьмой код и скажите, на сколько эти советы ускорили — безумно интересно.

Volshebnyi 23 июн 2011 в 21:36

Можно я попридираюсь? =)
В шестом листинге закралась ошибка, и в седьмом не исправилась. Появляется еcли n<2.
lst = n>=2 and [2] or []

Ano 23 июн 2011 в 22:17

Если уж придираться :)

lst = [2] if n >= 2 else []

SergeyBankevich 23 июн 2011 в 22:08

Только не понятно, почему j * j — 1. Просто j * j. Иначе, если i = 8, мы проверим j = 3, что излишне.

middle 24 июн 2011 в 06:26

На самом деле и без int((sqrt(i)+1) можно обойтись. Ведь при последовательном переборе при достаточно больших i значение либо увеличивается на 1, либо остаётся тем же ;)

Kilew 2 июл 2011 в 18:45

Вынос корня за пределы цикла дает бОльшую прибавку к скорости, нежели использование произведения
В моей реализации это давало ускорение до 10%

xanep 23 июн 2011 в 18:42

Поразительно. Вы начали писать программу, не зная про «Решето Эратосфена»?

simplecode 23 июн 2011 в 19:36

про это я знаю и что этот алгоритм работает быстрее тоже в курсе… спасибо… )

zzeus 23 июн 2011 в 22:27

тут можно схитрить, и сказать, что методы на основе решета Эратосферна не могут быть реализованы как генераторы (без ограничения предела генерации) и жрут память при больших n :P

xanep 24 июн 2011 в 04:10

Сказать можно. А можно подумать как сделать так, чтоб не жрало много памяти. Это я намекаю, что автору стоило именно в этом ключе думать ;)
В «Решете Эратосфена» без потери скорости алгоритма можно разбить большой диапазон на куски фиксированной длины. Например, по 1000 элементов. И найдя все простые от 1 до 1000, далее просеивать элементы от 1000 до 2000 и т.д.

Хотя об этом статья уже есть на хабре.

exponentum 23 июн 2011 в 21:23

Тоже по вашей теме.
stevegilham.blogspot.com/2009/01/pipe-operator-in-scala.html

Не знаю, правда, как по скорости работы. Но выглядит хорошо.

exponentum 23 июн 2011 в 21:24

Взято из поста на хабре, ссылку на который потерял.

ACTPOHABT 23 июн 2011 в 21:28

хабра скоро станет одной большой лекцией по математике, как например в данном случае по теории чисел )

iGloom 23 июн 2011 в 21:38

Вы так об этом говорите, будто это плохо.
Хабр — для It, и алгоритмы — вещь нужная.

ACTPOHABT 23 июн 2011 в 21:43

Не вижу, где это я говорю, что это плохо, особенно если учесть, что я по образованию математик

SergeyBankevich 23 июн 2011 в 22:05

Готов поспорить, что если убрать проверку на делимость на 5, станет только быстрее. А вот если правильным образом перебирать остатки при делении на 2 * 3 или 2 * 3 * 5, то должно ещё прирасти.
И ещё: обычно заводят внутри временную переменную, инициализируюмую как i и при нахождении делителя делят её сколько возможно на этот делитель. Тем самым, корень достигается быстрее.

aspect 24 июн 2011 в 08:43

∀p > 3 ∈ 6x ± 1

susl 23 июн 2011 в 22:09

> проверять только те числа, которые заканчиваются на 1, 3, 7 или 9
тогда лучше только эти числа и генерить для проверки, для этого можно развернуть цикл и убрать лишнее деление с остатком:

def test(i):
    for j in lst:
        if j*j-1 > i:
            lst.append(i)
            break
        if (i % j == 0):
            break
    else:
        lst.append(i)

m = 1
while True:
    m += 2
    if m > n: break
    test(m)
    m += 4
    if m > n: break
    test(m)
    m += 2
    if m > n: break
    test(m)
    m += 2
    if m > n: break
    test(m)

susl 23 июн 2011 в 22:10

а черт :) там еще 5 должно быть. но идею вы поняли

susl 23 июн 2011 в 22:12

т.е. случаи n <= 5 можно проверять отдельно

SergeyBankevich 23 июн 2011 в 22:13

Я примерно о том же. Но для эффективности будет невредно функцию заинлайнить.

susl 23 июн 2011 в 22:17

угу, надо бы. я просто не хотел чтоб пост разросся, только идею показать быстро :) даже про 5 забыл…

ACTPOHABT 23 июн 2011 в 22:09

Так как мне уже успели насрать в карму, то продолжу здесь писать. Интересны в данном контексте были бы полиномы, которые выдают простые числа. Сразу спешу расстроить: такого, который выдаёт только простые числа, не существует (Гольдбах, 1752). Эйлер же нашёл в 1772 одну совершенно необычную функцию: f_q(x)=x^2+x+q для всех x < q-1 если q из 2, 3, 5, 11, 17, 41.

ACTPOHABT 23 июн 2011 в 22:21

Также: любой алгоритм, основанный на сите Эратосфена, перестаёт быть эффективным для больших простых чисел, т.е. для действительно интересных чисел, нужных в криптографии. Для того, чтобы найти алгоритмы для настоящих простых чисел, приходится сначала прорубаться через понятия псевдопростых чисел и чисел Кармихаэля, через тесты для псевдопростых чисел Соловай-Штрасена, Рабин-Миллера итп.
Сегодня самыми эффективными можно считать тесты на простые числа при помощи эллиптических кривых, также известны APRCL и AKS. Подробнее писать в комментариях смысла, наверное, нет.

CleverMouse 24 июн 2011 в 08:47

Вы путаете области применимости алгоритмов: решето Эратосфена ищет все простые числа до некоторой границы, и именно эта задача обсуждается в посте; умные слова типа «псевдопростые числа» относятся к проблеме тестирования заданного числа на простоту.

ACTPOHABT 23 июн 2011 в 22:30

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

Можно сказать так: существуют простые двоичные числа любой длины!

ACTPOHABT 23 июн 2011 в 22:45

Но на самом деле всё намного круче: если вы покопаетесь в простых числах, то вы начнёте замечать, что они, ни смотря ни на какую случайность, довольно регулярны, и окажетесь правы конечно же.

Чейбышев доказал, что для любого n можно найти такие C_1 и C_2, что
C_1*n/log(n) < pi(n) < C_2*n/log(n),
где pi(n) это просто количество простых чисел меньше n.

Что показывает взаимосвязь натурального логарифма и простых чисел. Однако это ещё не всё! С помощью Чейбышева (но не только) можно доказать следующее:
lim_(x -> inf) pi(x)*log(x)/x = 1
Называется это Теорема о распределении простых чисел, на неё можно наглядно взглянуть тут: demonstrations.wolfram.com/ThePrimeNumberTheorem/.

SergeyBankevich 23 июн 2011 в 22:50

Умора. Чейбышев. Это ж надо.
Гражданин математик, прекратите монолог, состоящий из изложения элементарных фактов. Из википедии желающий найдёт всё перечисленное, а так же как пишется фамилия этого учёного.

ACTPOHABT 23 июн 2011 в 23:02

Sorry, учил все эти вещи не в русской литературе :(

ACTPOHABT 23 июн 2011 в 23:09

К тому же, по-моему как раз информация для человека, пишущего алгоритмы с ситом Эратосфена, самая подходящая.

hellman 24 июн 2011 в 10:29

Я бы не отказался почитать про интересные факты и теоремы из теории чисел, только желательно в виде статьи. В вики это не так просто, когда не знаешь что ищешь :)

SergeyBankevich 24 июн 2011 в 11:01

Специально зашёл сюда. Там написано всё вышеперечисленное со ссылками на описание.
Вцелом по т.ч. вы, наверное, правы.

hellman 24 июн 2011 в 11:10

Черт, сколько гулял по вики по всяким теоремам, а на страничку про простые числа не додумался зайти ) Спасибо

CleverMouse 24 июн 2011 в 11:06

Теория чисел — большая наука, там фактов и теорем много… Про распределение простых чисел с картинками на русском хорошо написано здесь: ega-math.narod.ru/Liv/Zagier.htm.

Bodigrim 24 июн 2011 в 13:09

Лучше рыться не в Вики, а в Mathworld. Например, Number Theory. Материалов и подробностей больше, но тексты сжатые и могут показаться слишком трудными для чтения.

Есть еще The Prime Pages, хотя вы их, наверное, уже видели по ссылкам из Вики. Там изложение достаточно доступное и темы менее специальные, чем на Mathworld.

Ну или скажите, что вам интересно по теории чисел — это моя специальность, могу подготовить материал. Если карма будет. Могу про эффективные алгоритмы некоторых теоретико-числовых вычислений, например. Не очень заумных, честно-честно. Могу про распределение простых чисел в контексте алгоритмов и оценки сложности алгоритмов.

AlexGl 26 июн 2011 в 14:43

Было бы очень классно алгоритм Берлекампа и Ленстра-Ленстра-Ловаса «на пальцах». Или ссылку, где они понятно объясняются. Спасибо!

CleverMouse 24 июн 2011 в 08:40

«Для любого n можно найти такие C_1 и C_2, что ...» — это не нуждается в доказательстве. Чебышёв доказал, что можно найти такие C_1 и C_2, что для любого (достаточно большого) n выполнены неравенства C_1*n/log(n) < pi(n) < C_2*n/log(n) — почувствуйте разницу. Чебышёву не удалось доказать, что предел существует; это сделали уже после него с использованием ~~тяжёлого матана~~ ТФКП.

ACTPOHABT 24 июн 2011 в 12:06

Вы совершенно правы! сам удивлён, что сформулировал теорему настолько неправильно.

Bodigrim 24 июн 2011 в 12:07

Сейчас известны намного более сильные факты: например, для достаточно большого n между n и n+n^0.525 всегда найдется простое число.

CleverMouse 24 июн 2011 в 08:44

Формулируйте чётче, в математике, равно как и в программировании, небольшое изменение слов может диаметрально изменить смысл и верность утверждения. Многочлен, выдающий в точности все простые числа, существует, с поправкой на то, что рассматривать нужно только положительные его значения; только такой многочлен зависит от 26 переменных.

daeto 24 июн 2011 в 10:27

Да, и этот многочлен не менее красив, чем теоремы Матиясевича. Тоже Сизого читали?)
Это я к тому, что интересующимся теорий чисел не помешает эта книга: Сизый С. В. Лекции по теории чисел.

Dembel 24 июн 2011 в 14:18

«и тут Остапа понесло...»(с)

Anexroid 24 июн 2011 в 00:34

А «решето Эратосфена» для чего? Зачем изобретать велосипед?

Не, я конечно понимаю, что всем всегда хочется написать своё. Но зачем, зачем?!

monitorika 24 июн 2011 в 04:04

Если бы Эратосфен когда то не хотел придумать что то своё, то сейчас мы бы не знали что существует «решето Эратосфена»…

Weageoo 24 июн 2011 в 04:32

Если мы постоянно будем изобретать велосипед, то 360 км/ч не разгоним никогда.

Я тоже недоумеваю, зачем этот алгоритм, если есть решето Эратосфена и современное решето Аткина. А тут и объяснено всё, и реализовано.

А сейчас, чтобы придумать что-то своё, нужно прежде много изучить, а потом уже сделать что-то лучше. Поверьте, гениально простые идеи на низких уровнях потихоньку исчерпались, и сейчас они гениально просты только для людей с достаточным уровнем знаний в той или иной области. Теорему Ферма тоже пыталось доказать много дилетантов (фермисты), толк от этого нулевой.

зы. Писать алгоритмы на Python — тенденция хорошая. Люблю этот язык.

Voenniy 24 июн 2011 в 05:34

Вот тут в 10 пунтке приводится пример нахождения простых чисел при помощи алгоритма Решето Эратосфен на разных языках программирования.

Вот пример для php:

for($i=range(2,100);($a[]=array_shift($i))&&count($i)>0;)
foreach($i as $k=>$v) if($v%end($a)==0) unset($i[$k]);

Kane 24 июн 2011 в 06:10

В тексте для поступления в Computer Science Center была задача на программирование в которой нужно было искать простые числа. Было интересно узнать, как много есть алгоритмов для нахождения их. Но там верхний предел был 10⁹.

dima_eam 24 июн 2011 в 06:38

Sorry за не в тему, тоже хочу поучавствовать cо своим APL:

Данное решение использует матрицу, содержащую все числа, кроме простых (видимо, то самое решето Эратосфена)

alno 24 июн 2011 в 08:28

Мне кажется, что вместо того, чтобы перебирать только те числа, которые оканчиваются на 1,3,7,9 (а это 2/5 всех чисел) будет еще немного эффективнее перебирать все числа вида 6k(±)1 — все простые числа кроме 2 и 3 имеют эту форму, их просто генерировать и их всего 1/3 от всех чисел.

savados 24 июн 2011 в 08:35

А если продолжить эту логику дальше, приходим к решету Эратосфена.

alno 24 июн 2011 в 08:39

Нет, это дополняет решето Эратосфена. Смотри мой комментарий ниже

alno 24 июн 2011 в 08:39

В догонку решето Эратосфена на Haskell:

eratosthenes (x:xs) = x:eratosthenes (filter ((/= 0).(`mod` x)) xs)

primes = eratosthenes 2 : 3 : [ 6*n+z | n <- [1..], z <- [-1,1] ]

Vladson 24 июн 2011 в 10:49

решето Эратосфена

Я его на ASM на спектруме как то делал, весёлая штука, но вот с практической точки зрения увы не самый «смак», слишком огромен простор для оптимизации

alno 24 июн 2011 в 08:41

Хотя решето Эратосфена позволяет эти числа отсеить, но тут выгода в том, что их можно генерировать (что значительно сократит перебор) и уже затем сгенерированный ряд передавать как основу для решета Эратосфена

simplecode 24 июн 2011 в 09:30

Слово «решето» уже 11 раз встретилось в комментариях, поэтому решил набросать этот алгоритм на Python и сравнить… Листинг 8 добавил в пост… Начиная, примерно с n = 140 «решето» работает быстрее…

SaveTheRbtz 13 июл 2011 в 20:22

Довольно быстрое решето на питоне, жаль, только, что не генератор.

def sieve(n):
        s = xrange(3, n + 1, 2)
        r = set(s)
        [r.difference_update(xrange(n << 1, s[-1] + 1, n)) for n in s if n in r]
        return r.union([2])

Вот статья на wikibooks про генерацию праймов на разных языках.

ПС. Кстати, там рядом есть тема, где человек страдает прям как вы.

sylvio 24 июн 2011 в 11:48

Это топик про нахождение простых чисел, так? Тогда добавьте оценку асимптотиечкой сложности к вашим алгоритмам, а питоновые хаки пишите как отдельный топик — они не интересны.

burdakovd 24 июн 2011 в 17:52

Спасибо за конструкцию for-else.

DjoNIK 25 июн 2011 в 14:25

Безотносительно алгоритма…
Я в свое время (еще в школе) обнаружил такую закономерность — начиная с простого числа 11, путем прибавления 30 получаем простое число. Уже не помню, но в этой закономерности были очень редкие исключения, например 19 + 30 = 49 = 7 * 7.

Bodigrim 26 июн 2011 в 11:50

Ваша закономерность объясняется тем, что числа вида 30k+p, где p — выбранное простое, большее 5, гарантированно не имеют делителей меньше 7, которые и высевают основную массу (~75%) составных чисел. В таких арифметических прогрессиях (30k+p) всегда бесконечно много простых чисел (теорема Дирихле), хотя при больших k большинство элементов окажутся все же составными.

qmax 26 июн 2011 в 09:24

а почему без yield?

ykrop 27 июн 2011 в 14:09

я не пойму, сегодня день абитуриентов на хабре?
первый курс, первый семестр, первый практикум: нахождение НОД, НОК и простых чисел в диапазоне. и это не говоря уже о том, что давно найден эффективный алогритм поиска простых чисел

Зарегистрируйтесь на Хабре, чтобы оставить комментарий