Sàng của chương trình python eratosthenes

Ý tưởng là tập trung vào việc triển khai các thuật toán và cấu trúc dữ liệu quan trọng cơ bản cho các vấn đề rất cơ bản. Những cấu trúc dữ liệu này không đầy đủ, nhưng đây là những thuật toán mà chúng ta thỉnh thoảng bắt gặp. Điều này sẽ giúp theo hai cách

• Học thuộc lòng những hiểu biết và cơ chế chính xác về các thuật toán
• Phát triển Mẫu cho các cấu trúc dữ liệu và thuật toán phổ biến để sử dụng lại sau này

Ghi chú

1. Khi sử dụng python, hãy sử dụng pypy trong các cuộc thi, nếu có, khi giải các câu hỏi vì đây là giải pháp thay thế nhanh hơn cho cpython. Chỉ cần đọc về nó

2. Tất cả các công ty FAANG hầu như chỉ tập trung vào các thuật toán này. Đây là thuật toán đòn bẩy cao từ góc độ phỏng vấn

Danh sách cấu trúc dữ liệu và giải thuật

• [Hai con trỏ] Thuật toán Floyd [Rùa và Thỏ]
• [Hai con trỏ] Trạng thái cũ và mới
• [Hai con trỏ] Bắt đầu và kết thúc cửa sổ trượt
• Danh sách liên kết
• Danh sách liên kết đôi
• Danh sách liên kết vòng
• Bảng băm
• Cây rơm
• ngăn xếp đơn điệu
• Xếp hàng
• ví dụ đệ quy
• Phân chia và chinh phục
• Sắp xếp chèn
• Hợp nhất Sắp xếp/[Hai con trỏ] Con trỏ-1 và con trỏ-2 từ hai chuỗi
• Sắp xếp bong bóng
• Sắp xếp lựa chọn
• Sắp xếp nhanh chóng
• sắp xếp đếm
• [Thống kê đơn hàng] Chọn nhanh
• Tìm kiếm nhị phân/ [Hai con trỏ] Ranh giới trái và phải
• Tìm kiếm nhị phân [sử dụng bisect]
• Đống/Hàng đợi ưu tiên
• Trie
• cán băm
• Tập rời rạc
• Cây nhị phân
• Cây tìm kiếm nhị phân
• Danh sách kề
• Ma trận kề
• Danh sách cạnh
• Tìm kiếm đầu tiên theo chiều rộng
• Độ sâu tìm kiếm đầu tiên
• Duyệt cây [Đặt hàng, Đặt hàng trước, Đặt hàng sau, Thứ tự cấp độ]
• Thuật toán Dijkstra [Hàng đợi ưu tiên]
• Thuật toán Bellman Ford
• Thuật toán Floyd Warshall
• Thuật toán Prim
• Thuật toán Kruskal
• Đường đi/Mạch Euler
• Thuật toán của Kosaraju [Các thành phần được kết nối mạnh mẽ]
• Phát hiện Chu kỳ trong biểu đồ [Lùi/Chuyển tiếp/cạnh cây]
• Sắp xếp tô pô
• quay lui
• Knapsack thuật toán tham lam
• Lập trình động Từ trên xuống DP
• DP từ dưới lên
• DP với mặt nạ bit
• Thuật toán Euclid [Ước chung lớn nhất]
• Thuật toán lũy thừa [Lũy thừa bằng bình phương D&C]
• Sàng Eratosthenes

Đối với các chủ đề nâng cao hơn và đi sâu vào lập trình cạnh tranh, hãy tham khảo cuốn sách này. https. //cses. fi/cuốn sách/cuốn sách. pdf theo đề xuất của các lập trình viên hàng đầu

Tôi bắt gặp một số điều mới về python khi học. Đôi khi bạn cũng có thể bắt gặp những thứ này. Đọc trước các blog này để được trợ giúp hiểu chúng, để bạn không bị mắc kẹt như tôi

1. https. //sách. đầu trăn. com/en/latest/for-otherse. html
2. https. // stackoverflow. com/câu hỏi/1907565/c-and-python-different-behaviour-of-the-modulo-operation
3. .
4. https. // stackoverflow. com/a/9674327/6725646

Tham chiếu kích thước đầu vào và độ phức tạp thời gian

Kích thước đầu vàoĐộ phức tạp thời gian mục tiêun ≤ 12O[n. ]n ≤ 25O[2^n]n ≤ 100O[n^4]n ≤ 500O[n^3]n ≤ 10 000 O[n^2]n ≤ 1 000 000 O[n log n]n ≤ 100 000

gợi ý

Có bất kỳ thuật toán nào khác mà tôi có thể bị thiếu không? . Hãy cùng nhau học hỏi

Để in tất cả các số nguyên tố nằm giữa hai số nguyên, hàm check_prime[] được tạo. Hàm này kiểm tra một số có phải là số nguyên tố hay không

Tất cả các số nguyên giữa n1 và n2 được truyền cho hàm này

Nếu một số được truyền cho check_prime[] là số nguyên tố thì hàm này trả về true, nếu không thì hàm trả về false

Nếu người dùng nhập số lớn hơn trước, chương trình này sẽ hoán đổi các số. Nếu không trao đổi, chương trình này sẽ không hoạt động

1. Ví dụ về cách giải các bài tập và bài toán thực hành bằng ngôn ngữ lập trình Python, bao gồm các thuật toán đã biết [tìm kiếm nhị phân, thuật toán Euclide, sàng Eratosthenes, tính giai thừa, chuỗi Fibonacci, tìm ước chung lớn nhất và bội chung nhỏ nhất]. Một số ví dụ chứa nhận xét chi tiết

phần. thuật toán tuyến tính, điều kiện, chu trình, chuỗi, danh sách, từ điển, hàm, tệp

2. Ví dụ về việc sử dụng các hàm dựng sẵn của Python và các phương thức của các lớp cơ sở - chuỗi, danh sách, từ điển, bộ, đối tượng tệp

Ví dụ về xử lý ngoại lệ, trình diễn các tính năng của lập trình hướng đối tượng trong Python, ví dụ về hiểu danh sách

3. Trình diễn các tính năng cơ bản của một số mô-đun của thư viện chuẩn Python - ngày giờ, lịch, thời gian, ngẫu nhiên, os và os. con đường

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?

vi. wikipedia. tổ chức

Sàng Eratosthenes

Trong toán học, sàng Eratosthenes là một thuật toán cổ xưa để tìm tất cả các số nguyên tố cho đến bất kỳ giới hạn nào. Nó làm như vậy bằng cách đánh dấu lặp đi lặp lại dưới dạng hỗn hợp [i. e. , không phải số nguyên tố] bội của mỗi số nguyên tố, bắt đầu bằng số nguyên tố đầu tiên, 2. Các bội số của một số nguyên tố đã cho được tạo thành một dãy số bắt đầu từ số nguyên tố đó, với hiệu không đổi giữa chúng bằng với số nguyên tố đó. Đây là điểm khác biệt chính của sàng so với việc sử dụng phép chia thử nghiệm để kiểm tra tuần tự

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 đó?

Làm cách nào để mã sàng của Eratosthenes trong Python?

Sàng trong Python là gì?

Phương pháp sàng Eratosthenes là gì?

Cách nhanh nhất để lấy số nguyên tố trong Python là gì?