Đó không phải là Sàng của Eratosthenes, mặc dù nó trông giống như vậy. Đó là trong thực tế tồi tệ hơn nhiều. Sàng là thuật toán tốt nhất để tìm số nguyên tố.
Xem http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
chỉnh sửa: Tôi đã sửa đổi https://stackoverflow.com/a/9302299/711085 là một one-liner (ban đầu nó không thực sự Sieve, nhưng bây giờ nó là ... có lẽ ...):
reduce((lambda r,x: r-set(range(x**2,N,x)) if (x in r) else r),
range(2,N), set(range(2,N)))
Demo:
>>> primesUpTo(N): lambda N: reduce(...)
>>> primesUpTo(30)
{2, 3, 5, 7, 11, 13, 17, 19}
Đáng buồn là tôi nghĩ rằng mặc dù điều này có hiệu quả trong ngôn ngữ lập trình hàm, nhưng nó có thể không hiệu quả trong trăn do cấu trúc dữ liệu không liên tục (chia sẻ trạng thái và bất biến), và bất kỳ rây nào trong python sẽ cần phải sử dụng đột biến đạt được hiệu suất tương đương. Chúng ta vẫn có thể nhồi nhét nó thành một lớp lót nếu chúng ta muốn tuyệt vọng. Nhưng trước tiên...
sàng bình thường:
>>> N = 100
>>> table = list(range(N))
>>> for i in range(2,int(N**0.5)+1):
... if table[i]:
... for mult in range(i**2,N,i):
... table[mult] = False
...
>>> primes = [p for p in table if p][1:]
>>> primes
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Chúng tôi bây giờ có thể xác định và gọi chức năng ẩn danh trên cùng một dòng, cũng như việc hack của [...].__setitem__ để làm đột biến nội tuyến, và hack của ... and foo để đánh giá ... khi trở về foo :
>>> primesUpTo = lambda N: (lambda table: [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] for i in range(2,int(N**0.5)+1) if table[i]] and [p for p in table if p][1:])(list(range(N)))
>>> primesUpTo(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
tiếp tục co rúm người trong nỗi kinh hoàng, the one-liner mở rộng (kỳ quặc đẹp bởi vì bạn có thể gần như trực tiếp dịch kiểm soát dòng chảy, nhưng một sự lạm dụng khủng khiếp của tất cả mọi thứ):
lambda N:
(lambda table:
[[table.__setitem__(mult,False) for mult in range(i**2,N,i)]
for i in range(2,int(N**0.5)+1) if table[i]]
and [p for p in table if p][1:]
)(list(range(N)))
phiên bản đột biến một lót này đã từ bỏ vào khoảng 10 trên máy tính của tôi, trong khi phiên bản mutating gốc đã từ bỏ vào khoảng 10 , chạy ra khỏi bộ nhớ (kỳ quặc).
Bản gốc reduce phiên bản đã hết tại 10 . Vì vậy, có lẽ nó không phải là rằng không hiệu quả sau khi tất cả (ít nhất là cho số bạn có thể đối phó với trên máy tính của bạn).
edit2 Có vẻ như bạn có thể lạm dụng tác dụng phụ ngắn gọn hơn như:
reduce((lambda r,x: (r.difference_update(range(x**2,N,x)) or r)
if (x in r) else r),
range(2,N), set(range(2,N)))
Nó cung cấp cho lên khoảng 10 , giống như các phiên bản đột biến một lót.
EDIT3: này runs at O (N) empirical complexity, trong khi nếu không có sự difference_update nó chạy ở O(n^2.2) complexity.
Hạn chế phạm vi đó được giảm xuống kết thúc, đến sqrt của giới hạn trên, và làm việc with odds only, cả hai kết quả trong thêm tốc độ-up (2x và 1.6x tương ứng):
reduce((lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r)
if (x in r) else r),
range(3, int((N+1)**0.5+1), 2),
set([2] + range(3,N,2)))
Nếu bạn có thể sống với một tổ chức phi oneliner, có câu hỏi này: http://stackoverflow.com/questions/567222/simple- máy phát điện nguyên tố-in-python – Andy
có thể trùng lặp của [Python-Sieve of Eratosthenes- Compact Python] (http://stackoverflow.com/questions/6687296/python-sieve-of-eratosthenes-compact-python) – ninjagecko
Tôi đã có thể để làm điều đó trong hai dòng: http://stackoverflow.com/a/9302299/5987 –