Лучший алгоритм на простых числах

Я работаю над программой, которая найдет n-й. простое число. Например, перечисляя первые шесть простых чисел: 2, 3, 5, 7, 11 и 13, мы видим, что шестое простое число равно 13. Я пытаюсь создать алгоритм, например, если я хочу увидеть 50-е простое число, я добавлю 1 к концам функции range(). В настоящий момент я использую этот алгоритм для поиска простых чисел;

cnt = 1
print (2)
for x in range(3,40,2):
    div = False
    for y in range(2,round(x**0.5)+1):
        if x%y == 0:
            div = True
    if div == False:
        print (x)
        cnt += 1

print ("\nThere is {} prime numbers.".format(cnt))

Вы видите, я поставил 40. Но я хочу поместить туда n, поэтому, например, до 50-го простого числа добавьте +1 к n. Но это не понравится, если я попробую что-то вроде;

cnt = 1
n = 40 #example
while cnt<50:
    for x in range(3,n,2):
        #codes
    if div == False:
        n += 1

Я думал, что когда программа найдет простое число, она добавит +1 к n, и цикл while будет обрабатывать, пока не найдет 50-е простое число. Но это не так, простые числа ошибочны, если я тоже использую это, ничего не имеет отношения к тому, что я хочу сделать.

  • Как сделать этот алгоритм, явно меняя последний элемент range(), функция не работает.

  • Есть ли лучший / элегантный алгоритм / способ? Если я хочу найти 200.000th простое число, мне нужны более быстрые коды.

Изменить: сначала я работал со списками, но у меня постоянно возникала ошибка MemoryError при работе с большими числами. Я передаю это и использую переменную, которая подсчитывает количество простых чисел cnt.


python algorithm python-3.4 primes
person GLHF    schedule 03.02.2015    source источник
comment
Что касается лучшего алгоритма, вы можете использовать Сито Эратосфена внутри диапазона, указанного в этот ответ math.SE   -  person Sinkingpoint    schedule 04.02.2015
comment
@Quirliom Спасибо за ваш комментарий, Создайте список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n). как вы видите в этом правиле, create список, который выдаст ошибку MemoryError при работе с большими числами, поэтому я перехожу к работе со списками.   -  person GLHF    schedule 04.02.2015
comment
У вас не должно быть ошибок памяти на <10 ** 8 - сколько у вас свободной оперативной памяти?   -  person user3467349    schedule 04.02.2015
comment
@ user3467349 Я всегда получал эту ошибку, если добавлял большое число в список, на самом деле я не знаю, почему. Думаю, около 4-5Гб.   -  person GLHF    schedule 04.02.2015
comment
Это из-за docs.python.org/2/library/sys.html # sys.maxsize   -  person user3467349    schedule 04.02.2015
comment
Я предполагаю, что во втором фрагменте кода есть cnt += 1, который был пропущен?   -  person Joel    schedule 04.02.2015
comment
@Joel Я не писал этого во втором коде, потому что я просто хочу показать, в чем была моя логика, но cnt подсчет количества простых чисел   -  person GLHF    schedule 04.02.2015
comment
17984? даже итерация с небольшими числами должна выполняться быстро.   -  person user3467349    schedule 04.02.2015
comment
Просто небольшое примечание, что я обновил свой ответ, включив в него тест, которым я пренебрегал. Теперь он прекращает тестирование, когда достигает простого числа больше sqrt (кандидата). Это тест, который вы использовали в своем коде, но я не включил его.   -  person Joel    schedule 04.02.2015

Ответы (2)


arrow_upward
3
arrow_downward

Вот гораздо более быстрая версия

primes = []
primecount = 0

candidate = 2
while primecount<50:
    is_prime = True
    for prime in primes:
        if candidate%prime == 0:
            is_prime = False
            break
        elif candidate < prime**2:
            break
    if is_prime:
        primes.append(candidate)
        primecount += 1

    candidate += 1
print primes[-1]

обратите внимание на небольшое изменение, добавив candidate<prime**2 тест, который был включен в OP, но я сначала пренебрегал.

Ваш код будет очень медленным по нескольким причинам. Если 2 делит число, вы знаете, что оно не простое, но вы все еще проверяете, делит ли его 3, 4 или 5 ... Так что вы можете вырваться, как только поймете, что это не прайм. Другая важная проблема заключается в том, что если 2 не делит число, нет причин проверять, делит ли и его 4 тоже. Таким образом, вы можете ограничить свое внимание простой проверкой того, делят ли его простые числа.

По времени выполнения:

введите описание изображения здесь

person Joel    schedule 04.02.2015
comment
Хороший алгоритм, это то, что я ищу. Спасибо за ответ - person GLHF; 04.02.2015
comment
Это алгоритм, предложенный вам @Quirliom. Я просто привел простую его реализацию. - person Joel; 04.02.2015
comment
Это не реализация Решета Эратосфена. Это оптимизированная версия пробного подразделения OPs. - person lvc; 04.02.2015
comment
Также кандидат может быть + = 2, чтобы пропустить эвены, и любопытно, что простое число на самом деле намного медленнее, чем for y in range(2,int(x**0.5+1)) - person user3467349; 04.02.2015
comment
выбор имени переменной вводит в заблуждение, поскольку вы используете простое число для перебора чисел и для логического значения. возможно, is_prime - лучший выбор для логического значения. - person Melug; 04.02.2015
comment
@Melug Спасибо - не заметил, что я использую prime двумя способами. Это действительно работает, но вы совершенно правы. Исправляем это сейчас. - person Joel; 04.02.2015
comment
@lvc нет, это хуже, чем код OP. сложность OP составляет N ^ 1,5 для верхнего предела N; этот код равен N ^ 2 / (log N) ^ 2. но да, это не SoE, сложность которого составляет N log (log N). Эмпирические порядки роста можно измерить. - person Will Ness; 04.02.2015
comment
@WillNess Вместо того, чтобы предлагать такую ​​косвенную критику, почему бы не сказать: «Эй, Джоэл, вы не добавили перерыв, если тестируемое простое число больше sqrt (кандидата)»? Я думал, что включил это, но вы правы, я не включил. Подскажите, пожалуйста, что теперь за масштабирование, когда оно реализовано правильно. - person Joel; 04.02.2015
comment
@Joel Тем не менее, это не the sieve of eratosthenes, пожалуйста, измените свой ответ, чтобы отразить это. - person sarveshseri; 04.02.2015
comment
@ Джоэл, я не знаю, есть ли что-то новое для тебя, верно? Так что это было обязательно косвенное, но вовсе не критика, а просто наблюдение. :) Сложность нового кода с добавленным пределом sqrt составляет N ^ 1.5 / (log N) ^ 2, AFAICR. Так что нет, это было немалое изменение, ни в коем случае. - Было бы очень интересно увидеть на этом графике время выполнения исходного кода (до редактирования). Кроме того, это может помочь визуальному восприятию графика, если вы разделите данные каждой строки на N и масштабируете каждую с помощью некоторой дополнительной константы, чтобы они начинались в одной точке. - person Will Ness; 04.02.2015
comment
Я предлагаю дополнительное масштабирование, так как, возможно, это позволит вам улучшить вертикальное разрешение графика (а может быть, в этом нет необходимости). Тогда я обязательно проголосую за этот ответ. - person Will Ness; 04.02.2015
comment
@WillNess - Вы правы, что это было не маленькое изменение с точки зрения его влияния, но это было совершенно очевидно незначительное изменение в том, что 1) OP имел его, поэтому было бы удивительно, если бы я не намеревался включать это и 2) это легкое, крошечное изменение. Это, очевидно, улучшает этот алгоритм для OP и любых будущих людей, использующих этот подход. Я не вижу здесь нашей роли в хранении таких вещей, чтобы не выдать ответ. Я добавлю запрошенное масштабирование к графику (скоро?), Но, вероятно, оставлю оригинал выключенным (не желая ждать, поскольку вы правы, что моя исходная ошибка замедлила работу) - person Joel; 05.02.2015
comment
@Joel спасибо за редактирование, и я проголосовал за; Теперь я думаю (извините за это :)), что лучше было бы разделить на фактическое время работы, поэтому это будет горизонтальной линией. Кроме того, нет необходимости в N ^ (3/2), необходимо N ^ (3/2) / (log N) ^ 2. У меня такое чувство, что в какой-то момент эта новая линия тоже станет горизонтальной. Это будет означать, что время работы будет одинаковым с точностью до постоянного коэффициента. Это может быть хорошей альтернативой вычислению коэффициентов мощности для последовательных диапазонов (как в статье WP), поскольку здесь также находят свое выражение постоянные коэффициенты, в отличие от этого метода. - person Will Ness; 05.02.2015

arrow_upward
-1
arrow_downward

Во-первых, для обратной совместимости с python 2 я добавил int() вокруг вашего округления корня x.

Насколько я понимаю ваш вопрос, вы ищете что-то вроде этого:

cnt = 1
maximum=50 #Specify the number you don't want the primes to exceed
print (2)
n=20 #highest number 
while cnt<maximum: #
    for x in range(3,n,2): #using "n" as you hoped
        div = False
        for y in range(2,int(round(x**0.5)+1)):
            if x%y == 0:
                div = True
        if div == False:
            if x<maximum: #we only want to print those up to the maximum
                print str(x)
            else: #if it is greater than the maximum, break the for loop
                break
            cnt += 1
    break #break the while loop too.
print ("\nThere are {} prime numbers.".format(cnt))

Это дало мне правильные простые числа. Что касается лучших / более элегантных решений. Если лучше вам нужна скорость, используйте библиотеку с оптимизированной версией или посмотрите this для примера быстрой программы. Элегантность субъективна, поэтому я оставлю это остальной части Интернета.

person IronManMark20    schedule 04.02.2015