Как я могу сделать свою основную генераторную функцию быстрее

Question

, чтобы получить практический опыт, я пытаюсь решить проблемы в spoj. Проблема в ссылке требует найти все простые числа между заданными 2 числами. Итак, как я реализую это с помощью python 2.7

# printing all prime numbers between given two inputs 
import math 
def findPrimes(num1,num2): 
    for num in range(num1,num2+1): 
     isPrime=True 
     for i in range(2,int(math.sqrt(num))+1): 
      if num%i==0: 
       isPrime=False 
       break 
     if isPrime: 
      print num 


def main(): 
    inputs=[] 
    numOfTestCases=int(raw_input()) 

    while(numOfTestCases>0): 
     line=raw_input() 
     numbers=line.split() 
     inputs.append(numbers) 
     numOfTestCases-=1 

    for testCase in inputs: 
     findPrimes(int(testCase[0]),int(testCase[1])) 
     print "" 

main() 

Однако, когда я отправляю код, я получаю предел превышения времени. Как я могу сделать свой код достаточно быстрым?

Answer 1

Вы должны использовать Sieve of Eratosthenes, и это довольно просто. Сначала вы инициализируете все числа, чтобы они были первыми. Тогда для каждого шага вы удаляете его кратные из основного списка. И это временная сложность, близкая к линейке O(nloglogn). Что-то вроде этого:

N = 1000 
is_prime = [1]*N 
for i in xrange(2,N): 
    if is_prime[i]: 
     for j in xrange(2*i,N,i): 
      is_prime[j] = 0 

Эта реализация должна выполняться в порядке. Но есть некоторые дополнительные оптимизации, которые вы можете найти в приведенной выше ссылке.
Обратите внимание, что 0 и 1 не являются первичными.

Answer 2

Нет, цифры не огромны в spoj/PRIME1. Решетка Эратосфена работает там очень хорошо, но даже пробное подразделение позволяет вам пройти там, если вы проверите по простым символам и испытайте коэффициенты (или лучше всего, только 6-coprimes или 30-coprimes).

Вам нужно только найти простые числа ниже квадратного корня верхнего предела, заранее. sqrt(10^9) составляет около 32 000, поэтому для поддержания есть только около 3,400 простых чисел. Это ничего.

---

6-coprimes: числа взаимно просты с 6, то есть с 2 и 3, так что нет необходимости проверять разделить их на 2, ни 3, при проверке простых чисел. Вам нужно найти способ их генерировать напрямую, поэтому не должно быть кратных 2 и 3 числа, которое необходимо проверить, по строительству.