Sàng của danh sách Python của Eratosthenes

Như ta đã biết, số nguyên tố là số tự nhiên có đúng hai ước số tự nhiên phân biệt. số 1 ​​và chính nó

Chúng tôi thường nhận được những câu hỏi như câu hỏi dưới đây

Cho một số n, in ra tất cả các số nguyên tố nhỏ hơn hoặc bằng n. - e. g. Nếu n là 20, đầu ra phải là “2, 3, 5, 7, 11, 13, 17, 19”

Sàng của Eratosthenes được sử dụng để lấy tất cả các số nguyên tố trong một phạm vi nhất định và là một thuật toán rất hiệu quả. Bạn có thể đọc thêm về sàng của Eratosthenes trên Wikipedia

Trong thuật toán này, chúng ta làm theo các bước sau để lấy các số nguyên tố lên đến n [giả sử n = 12]

1. Đầu tiên, chúng ta tạo một danh sách boolean có độ dài n+1 chứa đầy tất cả True như.
   ______4
2. Vì 0 và 1 không phải là số nguyên tố nên ta đặt hai phần tử đầu tiên của danh sách là Sai. Vì vậy, bây giờ danh sách của chúng tôi là.
   ______5
3. Bắt đầu từ 2, chúng tôi đặt các phần tử tại chỉ mục là bội số của 2 thành Sai, ngoại trừ chính nó. Vì vậy, danh sách của chúng tôi trở thành.
   ______6
4. Lặp lại bước 3 cho đến căn bậc hai của n [i. e. √12 trong ví dụ này]. Cuối cùng, danh sách của chúng tôi trở thành.
   ______7
5. Danh sách còn lại chỉ chứa True tại chỉ mục là số nguyên tố

Mã này là một đại diện đơn giản của các bước được đề cập ở trên

Trước tiên, chúng tôi tạo một danh sách boolean với tất cả các giá trị được khởi tạo bằng True. Một giá trị sẽ là Sai nếu nó không phải là số nguyên tố khác Đúng. Sau đó, chúng tôi bắt đầu lặp lại từ 2 cho đến căn bậc hai của số và cập nhật bội số thành Sai. Điều này được thực hiện bằng cách sử dụng vòng lặp 'for' khác từ 2*i đến n+1 với bước j+1

Cuối cùng, chúng tôi nhận được danh sách cuối cùng của mình và kiểm tra các giá trị. Nếu giá trị tại bất kỳ chỉ mục nào là True, điều đó có nghĩa là số đó là số nguyên tố và chúng tôi in số

Tôi đã kiểm tra sàng vấn đề mã hóa eratosthenes trên google và tôi đã tìm thấy bài viết về vấn đề này. Tôi đang chia sẻ một ví dụ mã hóa. Bất cứ ai có thể giải thích cho tôi, cách thức hoạt động của chương trình eratosthenes?

Lần đầu tiên bạn đọc mô tả về thuật toán, chẳng hạn như thuật toán này?

Mã bạn hiển thị không phải là cách tôi viết sàng

Mã mà bạn hiển thị làm là tạo một mảng, khai báo mọi giá trị trong
mảng là số nguyên tố [hoặc “có khả năng là số nguyên tố”], sau đó cho mỗi mục “đúng”< .
in the array:

• nó là số nguyên tố vì không có giá trị nào trước đó đã loại bỏ nó
• loại bỏ "tính nguyên tố" của tất cả các bội số của giá trị

Khi tôi viết thuật toán này, tôi hầu như xử lý mảng các số nguyên tố tiềm năng
. Tôi không tạo ra nó và thay vào đó, tôi chỉ giữ một danh sách
các số nguyên tố trước đó được tìm thấy cho đến nay. Sau đó, đối với mỗi số nguyên tố tiềm năng n, tôi kiểm tra
nó dựa trên tất cả các số nguyên tố trước đó cho đến sqrt[n]. Vì vậy, tôi không cần
giới hạn trên và không cần phân bổ mảng ban đầu; . Và tôi thường chỉ đếm những giá trị lẻ
a counter n from 3 upwards. And I usually only count the odd values
i. e. đếm bằng 2, vì tất cả các số chẵn được biết là không phải là số nguyên tố.

Tôi nghĩ rằng 2 cách tiếp cận có thể có chi phí thời gian chạy tổng thể tương tự nhau

Chúc mừng!
Cameron Simpson cs@cskk. Tôi. au

Điểm nổi bật của thuật toán Eratosthenes là bạn không bao giờ cần thực hiện phép chia, bạn có thể loại bỏ các giá trị không thể là số nguyên tố mà không cần kiểm tra xem chúng có phải là số nguyên tố hay không

Nếu bạn đang làm điều này

“Sau đó, đối với mỗi số nguyên tố tiềm năng n, tôi kiểm tra nó với tất cả các số nguyên tố trước đó cho đến sqrt[n]. ”

sau đó bạn không sử dụng sàng của Eratosthenes, bạn đang sử dụng một số thuật toán khác [có thể là phép chia thử nghiệm không ngây thơ hoặc có thể là thuật toán bánh xe]

Nhân tiện, khi bạn vượt qua hai số nguyên tố đầu tiên là 2, 3, bạn chỉ cần kiểm tra số ngay trước và ngay sau mỗi bội số của 6. Điều đó cho phép bạn bỏ qua việc kiểm tra 2 trên 3 số nguyên tố tiềm năng thay vì chỉ 1 trên 2 [các số chẵn]

[Đây cũng không phải là sàng của Eratosthenes. ]

def primes[]:

    yield 2

    yield 3

    i = 6

    while True:  # Run forever.

        a = i - 1

        b = i + 1

        if isprime[a]: yield a

        if isprime[b]: yield b

        i += 6

Có nhiều cách sắp xếp bánh xe phức tạp hơn có thể bỏ qua nhiều hơn

Tôi khuyên bạn nên đọc bài viết Wikipedia mà bạn đã liên kết đến và xem kỹ hoạt ảnh. Theo ý kiến ​​​​của tôi, hoạt ảnh có thể được cải thiện, nhưng nó đưa ra ý tưởng về quy trình

Có một phiên bản của sàng Euler phổ biến trong giới Haskell, nơi nó thường được mô tả sai là sàng của Eratosthenes

primes = sieve [2..]

sieve [p : xs] = p : sieve [x | x  0]

Đó là ngắn gọn thú vị, nhưng cực kỳ không hiệu quả. Hành vi tiệm cận tồi tệ hơn so với phân chia thử nghiệm

Phiên bản Python có thể là

def sieve[]:

    # Very slow, very inefficient version of Euler's sieve.

    nums = itertools.count[2]

    while True:

        prime = next[nums]

        yield prime

        nums = filter[lambda v, p=prime: [v % p] != 0, nums]

Tôi không biết liệu có thể viết một phiên bản sàng Euler hiệu quả hay không

Trong thử nghiệm hạn chế của riêng tôi, phương pháp nhanh nhất mà tôi tìm thấy để tạo ra các số nguyên tố nhỏ là phiên bản Croft Spiral này

def croft[]:

    # Implementation is based on erat3 from here:

    #   //stackoverflow.com/q/2211990

    # and this website:

    #   //www.primesdemystified.com/

    # Memory usage increases roughly linearly with the number of primes seen.

    # dict ``roots`` stores an entry p**2:p for every prime p.

    for p in [2, 3, 5]:

        yield p

    roots = {9: 3, 25: 5}  # Map d**2 -> d.

    primeroots = frozenset[[1, 7, 11, 13, 17, 19, 23, 29]]

    selectors = [1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0]

    for q in itertools.compress[

            # Iterate over prime candidates 7, 9, 11, 13, ...

            itertools.islice[itertools.count[7], 0, None, 2],

            # Mask out those that can't possibly be prime.

            itertools.cycle[selectors]

            ]:

        # Using dict membership testing instead of pop gives a

        # 5-10% speedup over the first three million primes.

        if q in roots:

            p = roots[q]

            del roots[q]

            x = q + 2*p

            while x in roots or [x % 30] not in primeroots:

                x += 2*p

            roots[x] = p

        else:

            roots[q*q] = q

            yield q

Tại một số thời điểm, khi bạn đạt được các ứng cử viên thực sự khổng lồ, việc lưu trữ tất cả các số nguyên tố đã thấy trước đó để thực hiện phép chia thử nghiệm trở nên không thực tế. Tại thời điểm đó, tôi đoán phương pháp thực tế duy nhất là hoán đổi sang phương pháp xác suất chẳng hạn như Miller-Rabin

Nếu Tim Peters ở đó, có lẽ anh ấy sẽ tranh luận ủng hộ việc chỉ sử dụng Miller-Rabin [được tăng cường bằng một vài phép thử chia thử nghiệm trên các số nguyên tố nhỏ để loại bỏ các hợp chất rõ ràng] cho mọi thứ. Nhưng đâu là niềm vui trong đó?