Sàng số nguyên tố nhanh trong Python

Question

Tôi đã trải qua quá trình tạo số nguyên tố bằng python bằng sàng của Eratosthenes và các giải pháp mà mọi người chào mời như một tùy chọn tương đối nhanh như trong một số ít the answers to a question on optimising prime number generation in python không đơn giản và đơn giản thực hiện mà tôi có ở đây đối thủ cạnh tranh chúng trong hiệu quả. thực hiện của tôi được đưa ra dưới đây

def sieve_for_primes_to(n): 
    size = n//2 
    sieve = [1]*size 
    limit = int(n**0.5) 
    for i in range(1,limit): 
     if sieve[i]: 
      val = 2*i+1 
      tmp = ((size-1) - i)//val 
      sieve[i+val::val] = [0]*tmp 
    return sieve 


print [2] + [i*2+1 for i, v in enumerate(sieve_for_primes_to(10000000)) if v and i>0] 

Thời gian thực hiện trả

python -m timeit -n10 -s "import euler" "euler.sieve_for_primes_to(1000000)" 
10 loops, best of 3: 19.5 msec per loop 

Trong khi phương pháp này được mô tả trong các câu trả lời cho câu hỏi liên kết ở trên như là nhanh nhất từ ​​sách dạy nấu ăn trăn được đưa ra dưới đây

import itertools 
def erat2(): 
    D = { } 
    yield 2 
    for q in itertools.islice(itertools.count(3), 0, None, 2): 
     p = D.pop(q, None) 
     if p is None: 
      D[q*q] = q 
      yield q 
     else: 
      x = p + q 
      while x in D or not (x&1): 
       x += p 
      D[x] = p 

def get_primes_erat(n): 
    return list(itertools.takewhile(lambda p: p<n, erat2())) 

Khi chạy nó cung cấp cho

python -m timeit -n10 -s "import euler" "euler.get_primes_erat(1000000)" 
10 loops, best of 3: 697 msec per loop 

Câu hỏi của tôi là tại sao mọi người lại yêu thích những điều trên từ cuốn sách nấu ăn tương đối phức tạp như máy phát điện chính lý tưởng?

Answer 1

Bạn chỉ nên sử dụng "postponed" variant of that algorithm. So sánh mã của bạn test run lên tới 10 đến 20 triệu đô la giới hạn trên, như

... 
print(len([2] + [i*2+1 for i, v in 
    enumerate(sieve_for_primes_to(10000000)) if v and i>0])) 

với một trong những khác, run at các con số tương ứng của 664.579 và 1.270.607 số nguyên tố để sản xuất, như

... 
print(list(islice((p for p in postponed_sieve()), n-1, n+1))) 

cho thấy đang chạy của bạn "chỉ" 3.1x ... 3.3x lần nhanh hơn. :) Không phải36x lần nhanh hơn vì thời gian của bạn hiển thị vì một số lý do.

Tôi không nghĩ rằng bất cứ ai từng tuyên bố đó là một máy phát điện nguyên tố "lý tưởng", chỉ là nó là một cái sạch khái niệm và rõ ràng. Tất cả các chức năng thế hệ chính là đồ chơi thực sự, những thứ thực sự đang làm việc với những con số rất lớn, bằng cách sử dụng các thuật toán hoàn toàn khác nhau.

Ở đây trong phạm vi thấp, điều quan trọng là độ phức tạp về thời gian của thuật toán, sẽ là khoảng ~ n^(1+a), a < 0.1...0.2empirical orders of growth, cả hai dường như thực sự là như vậy. Có một máy phát điện đồ chơi với ~ n^1.5 hoặc thậm chí ~ n^2 đơn đặt hàng tăng trưởng chỉ là không có niềm vui để chơi với.

Answer 2

tôi chuyển mã của bạn để phù hợp với kịch bản rây so sánh chính của @unutbu tại Fastest way to list all primes below N như sau:

def sieve_for_primes_to(n): 
    size = n//2 
    sieve = [1]*size 
    limit = int(n**0.5) 
    for i in range(1,limit): 
     if sieve[i]: 
      val = 2*i+1 
      tmp = ((size-1) - i)//val 
      sieve[i+val::val] = [0]*tmp 
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0] 

On MBPro tôi i7 kịch bản đang nhanh chóng tính toán tất cả các số nguyên tố < 1000000 nhưng thực sự 1,5 lần chậm hơn rwh_primes2, rwh_primes1 (1.2), rwh_primes (1.19) và primeSieveSeq (1.12) (@andreasbriese ở cuối trang).