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

Question

Я пытаюсь решить проблему, упомянутую здесь: https://www.spoj.pl/problems/PRIME1/

Я также даю описание ниже.

Питер хочет сгенерировать некоторые простые числа для своей криптосистемы.Помоги ему!Ваша задача - сгенерировать все простые числа между двумя заданными числами!

Ввод

Ввод начинается с числа t тестовых случаев в одной строке (t <= 10).В каждой из следующих t строк есть два числа m и n (1 <= m <= n <= 1000000000, nm <= 100000), разделенных пробелом. </p>

Выход

ДляВ каждом тестовом примере выведите все простые числа p, такие что m <= p <= n, по одному числу в строке, тестовые примеры отделены пустой строкой. </p>

Мой код такой, как показано ниже.Я думаю, что метод удаления в списке очень медленный.

import sys
import math

num = int(sys.stdin.readline());
indices = []
maxrange = 2
while(num > 0):
    a,b = sys.stdin.readline().split(" ");
    a = int(a)
    b = int(b)
    if(a < 2):
        a = 2
    indices.append((a,b))
    if(b > maxrange):
        maxrange= b          
    num = num - 1

val = int(math.sqrt(maxrange)+1)
val2 = int(math.sqrt(val)+1)
checks = range(2,val2)

for i in range(2,val2):
    for j in checks:
        if(i!= j and j%i == 0):
            checks.remove(j)

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

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):
            print p
        if(p > b):
            break
    print

Я думаю, что удаление списка Python очень медленное.Мой код верен, но превышен лимит времени.Может кто-нибудь помочь мне улучшить этот код.

Answer 1

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

Answer 2

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

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

Answer 3

Вот детерминистский вариант теста простоты Миллера-Рабина для маленьких нечетных целых чисел в 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

Целью кода является выполнение исполняемого псевдокода.

Answer 4

remove () не является медленным в общей схеме вещей, просто код называет это LOT.

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

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

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

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

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

From Python docs - 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):

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