Код простого числа Python работает медленно

Вместо того, чтобы удалять элемент, который не является простым числом, почему бы не заменить его каким-нибудь контрольным значением, например -1 или None? Затем при печати просто печатайте значения, которые не являются часовыми.

Используйте список длиной (n-m), а затем индекс для номера i равен x[m+i].

Функция проверки простоты будет работать лучше всего. Псевдокод есть на страница википедии Миллера-Рабина

remove() не является медленным по большому счету, просто код называет его МНОГО.

Как предлагает dappawit, вместо того, чтобы изменять список, измените значение в списке, чтобы вы знали, что это недопустимый номер для использования.

Я также вижу, что когда вы создаете набор простых чисел, вы используете range(2,maxrange), что нормально, но неэффективно, если нижняя граница намного больше 2. Вы будете тратить вычислительное время на создание простых чисел, которые даже не имеют отношения к проблемное пространство. Если ничего другого, следите за minrange, а также maxrange.

Ошибка с вашим исходным кодом заключается в том, что вы используете range(2,maxrange). Это означает, что maxrange нет в списке рассматриваемых номеров. Попробуйте 3 5 в качестве входных данных для a и b, чтобы увидеть ошибку.

range(2,maxrange+1) устраняет проблему.

Еще одна ошибка в коде заключается в том, что вы изменяете исходную последовательность:

Из документов по Python — for-statement

Небезопасно изменять повторяющуюся в цикле последовательность (это может произойти только для изменяемых типов последовательностей, таких как списки). Если вам нужно изменить список, по которому вы выполняете итерацию (например, чтобы дублировать выбранные элементы), вы должны выполнить итерацию по копии. Обозначение среза делает это особенно удобным:

Мои навыки работы с Python рудиментарны, но, похоже, это работает:

Старый:

primes2 = range(2,maxrange)
for i in primes:
     for j in primes2:
         if(j != i and j%i == 0):
             primes2.remove(j)

for (a,b) in indices:
    for p in primes2:
        if(a<= p and b >= p):

Новый:

primes2 = array.array('L', range(minrange,maxrange+1))
for i in primes:
    for j in primes2:
        if(j != i and j%i == 0):
            primes2[j-minrange] = 0

for (a,b) in indices:
    for p in primes2:
        if (p != 0):
            if(a<= p and b >= p):

Вы также можете пропустить создание набора простых чисел и просто протестировать числа напрямую, что сработает, если наборы чисел, которые вы должны сгенерировать, не перекрываются (без дублирования работы). введите здесь описание ссылки

Вот детерминированный вариант теста Миллера-Рабина на простоту для небольших нечетные целые числа в Python:

from math import log

def isprime(n):
    assert 1 < n < 4759123141 and n % 2 != 0, n

    # (n-1) == 2**s * d
    s = 0
    d = n-1
    while d & 1 == 0:
        s += 1
        d >>= 1
    assert d % 2 != 0 and (n-1) == d*2**s

    for a in [2, 7, 61]:
        if not 2 <= a <= min(n-1, int(2*log(n)**2)):
            break
        if (pow(a, d, n) != 1 and
            all(pow(a, d*2**r, n) != (n-1) for r in xrange(s))):
            return False
    return True

Намерение кода состоит в том, чтобы быть исполняемым псевдокодом.