打印給定範圍內的所有素數，算法太慢..如何改進？ （代碼挑戰）

Question

這是一個關於代碼挑戰的問題，請不要提供太多的代碼..我想盡可能地自己弄清楚這一點。

我最近開始進入代碼挑戰，並將其與學習Python（我是一個前端JavaScript開發者白天;））結合起來。到目前爲止，一切進展順利，我確信這是學習新語言的最佳方式（至少對我而言）。

我目前被困在一個挑戰，要求我打印給定範圍內的所有素數，這一切都是通過簡單的Stdin和Stdout完成的。

到目前爲止，我已經嘗試了兩種方法，兩者都在工作，但速度太慢..下面是一個鏈接和迄今爲止我的最快實現的代碼。也許我錯過了一些超級明顯的東西，導致我的python腳本變慢。目前，它需要1.76s單個測試用例的一系列1, 100000

http://ideone.com/GT6Xxk（你可以在這裏調試腳本以及）

from sys import stdin 
from math import sqrt, ceil 

next(stdin) # skip unecessary line that describes the number of test cases 

def is_prime(number): 
    initial_divider = sqrt(number) 

    if number == 2: 
     return True 
    elif number % 2 == 0 or int(initial_divider) == initial_divider: 
     return False 

    for divider in range(ceil(initial_divider), 1, -1): 
     if number % divider == 0: 
      return False 

    return True 

for line in stdin: 
    low, high = [int(x) for x in line.split(' ')] 
    primes = [number for number 
        in range(max(low, 2), high+1) 
        if is_prime(number)] 

    for prime in primes: 
     print (prime) 
    print('') 

的「分配」的/挑戰是如下的描述：

輸入

輸入開始的測試用例在一行數噸（噸< = 10）。在每個接下來的t行中，有兩個數字m和n（1 < = m < = n < => 1000000000，n-m < = 100000）由空格分隔。

輸出

對於每個測試實例打印所有素數p使得m < = P < = n時，每行一個數>，測​​試用例由空行分隔。

更新1：我清理的最後一個塊，其中質數和印刷的聚會做的邏輯：

for line in stdin: 
    low, high = [int(x) for x in line.split(' ')] 
    for number in range(max(low, 2), high+1): 
     if is_prime(number): 
      print (number) 
    print('') 

Answer 1

1）它可能是控制檯IO主導，打印輸出。我改變了輸出，所以它使用一個生成器來收集素數，將數字轉換爲字符串，然後用換行符連接數字。這應該在列表構建中節省一些內存，並將一些Python列表迭代向下推送到Python運行時。這使得我在PC上進行不科學的衝擊測試的速度提高了約30％，對ideone沒有太大的影響。 （這可能是因爲我讓它運行在Python 2中，它有一些非常不同的迭代/列表/生成器工作，但在ideone上使用Python 3）。

2）您每次運行if number == 2: return True測試;在前100,000個數字中，大多數不是2.我提取它打印2，然後打印其餘的素數。非常小的變化，並不值得。

3）您的範圍數減少 - range(ceil(initial_divider), 1, -1) - 這真的很奇怪。一個數字很可能會被3除以19，每第三個數字除以3，只有每19個數字除以19.所以對於快速返回的功能，先試試小分割器吧？我把它設置爲up。顯而易見的速度提升，我希望它仍然有效。

這是原始運行時間的約50％，處於一種偶然且完全無法比擬的情況。代碼現在看起來是這樣的：

from sys import stdin 
from math import sqrt, ceil 

next(stdin) # skip unecessary line 

def is_prime(number): 
    initial_divider = sqrt(number) 

    if number % 2 == 0 or int(initial_divider) == initial_divider: 
     return False 

    for divider in range(2, ceil(initial_divider)+1): 
     if number % divider == 0: 
      return False 

    return True 

for line in stdin: 
    low, high = [int(x) for x in line.split(' ')] 
    primes = '\n'.join(str(number) for number 
        in range(max(low, 3), high+1) 
        if is_prime(number)) 

    if low <= 2: print(2) 
    print (primes) 
    print('') 

Answer 2

更改列表解析生成器，腳本的運行速度更快。

for number in range(max(low, 2), high+1): 
    if is_prime(number): 
     yield number 

Answer 3

def PrimesBelow(limit): 
    np=set() 
    p=[2] 
    for i in xrange(1,limit+1,2): 
      if i == 1: continue 
      if i in np: continue 
      beg=2 if i % 2 == 0 else 0 
      for j in xrange(beg,int(limit)+1,i): 
        np.add(j) 
      p.append(i) 
    return i 

LetzerWille是正確的。上面的函數將返回一個低於（限制）的素數列表。我認爲這個函數的運行速度比檢查每個數字是否爲素數還要快，因爲這個函數將刪除乘以的每個數字，並將它們添加到（np）。注意：這個功能只會測試奇數。

Answer 4

在像C或C++這樣的語言中，SPOJ PRIME 1問題很容易通過暴力破解來解決，即通過編寫代碼在不到一秒的時間內將所有數字篩選到1000,000,000並因此保持在時間限制之下。甚至可能在Java，C＃或Delphi中。但是，如果在Python中有可能，那麼它可能是血腥的，並且需要一些嚴重的fu。

但是請注意，SPOJ PRIME 1不要求過濾十億個數字;它要求篩分的幾個小範圍不超過100001個數，並且它可能只查詢少數幾個範圍。假設範圍數爲100（可能少得多），平均寬度爲100000（可能少得多），那麼仍然只有10,000,000個數字。在這種情況下篩分十億美元的工作量太多了，這就是爲什麼SPOJ PRIME 1儘管學者們使用的語言種類繁多，仍然能夠以如此精確的方式清除穀殼。

因此，訣竅是隻做要求 - 篩選作爲輸入提供的範圍。即使是最簡單，直接的代碼也可以用很多時間做到這一點（C++：大約總共毫秒）。該原則與我在回答challenge of drawing 100 random primes from a range with an upper bound of 1,000,000,000時的原理完全相同，並且適用相同的解決方案。關鍵是編寫一個函數，可以篩選給定的範圍（窗口），而無需篩選下面的所有數字。

此外，如何擊敗SPOJ PRIME 1的問題已經被問及很多次了，而且給出的答案仍然有效。一個小的選擇：

• How do I efficiently sieve through a selected range for prime numbers?
• Efficient algorithm to get primes between two large numbers
• Generating prime numbers between m and n
• SPOJ PRIME1 : TLE
• Segmented Sieve of Erastothenes C++ SPOJ
• Spoj PRIME1 using sieve of eratosthenes (in C)
• ...

Answer 5

簡單的改進。看到這個簡單的代碼讓人不好意思。我的時間更長，速度更慢:(...但我學到了很多:)

添加也很簡單函數的測量時間MT（）

def PrimesBelow(limit): 
    np=set() 
    p=[2] 
    for i in range(3,limit+1,2): 
      if i in np: continue 
      beg = i*i 
      for j in range(beg,int(limit)+1,i): 
        np.add(j) 
      p.append(i) 
    return p 

def mt(n): 
    import time 
    t = time.time() 
    pr = PrimesBelow(n) 
    print("#-Primes: {}, Time: {}".format(len(pr), round(time.time()-t, 4))) 
    return pr 

pr = mt(100000000) 

是與16GB一個i7-3770的反饋