有人可以幫助解釋爲什麼這種尋找素數的方法比我的要快得多嗎？

Question

我幾天前纔開始編程，並試圖解決涉及質量最大的問題。這裏是我想出了一個方法，但有大量很慢：

import time 
import math 

t0=time.clock() 

a=100000 

##preprimes is the list of primes up to sqrt(a) that will be 
##divided into the larger list lista 


preprimes=[] 

lista= list(range(1,a)) 
prelista= list(range(1,round(math.sqrt(a)))) 

def predivisors(a): 
    x=a-1 
    suma=0 
    while (x>0): 
     if a%x==0: 
      suma=suma+x 
      x=x-1 
      if suma==1: 
       preprimes.append(a) 
     else: 
      x=x-1   

for x in prelista: 
    predivisors(x) 


for n in preprimes: 
    for num in lista: 
     if num%n==0: 
      lista.remove(num) 

print(sum(lista)+sum(preprimes)-1) 
print(time.clock()-t0, ' seconds') 

這種方法需要81秒返回素數之和高達100萬。我在網上找到的以下方法需要0.38秒才能完成同樣的任務：

import math 
import time 

t0=time.clock() 

n=100000 

def getPrimes(n): 
    """returns set of all primes below n""" 
    non_primes = [j for j in range(4, n, 2)] # 2 covers all even numbers 
    for i in range(3, n, 2): 
     non_primes.extend([j for j in range(i*2, n, i)]) 
    return set([i for i in range(2, n)]) - set(non_primes) 


def getCircularPrimes(n): 
    primes = getPrimes(n) 
    is_circ = [] 
    for prime in primes: 

     prime_str = str(prime) 
     iter_count = len(prime_str) - 1 

     rotated_num = [] 
     while iter_count > 0: 
      prime_str = prime_str[1:] + prime_str[:1] 
      rotated_num.append(int(prime_str)) 
      iter_count -= 1 

     if primes >= set(rotated_num): 
      is_circ.append(prime) 


    return len(is_circ) 

print(sum(getPrimes(n))) 
##print(sorted(getPrimes(n))) 

print('process took ',time.clock()-t0,'seconds') 

爲什麼第二種方法比我的要快得多？什麼因素決定了一個過程需要多長時間？

Answer 1

在您的方法中，您根據n評估n號碼列表與另一個大號數字列表。 這樣做你執行大量任務

for n in preprimes: 
    for num in lista: 
     if num%n==0: 
      lista.remove(num) 

的，我相信這將導致一個時間複雜度某處O(n^2)範圍

看到http://en.wikipedia.org/wiki/Time_complexity

在在線方式我認爲它更接近於複雜性O(n)

O(n)和O(n^2)之間的運行時差異隨着輸入n的增長而急劇上升。