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

Hãy viết mã thuật toán Sàng của Eratosthenes cho các số nguyên tố bằng Python. Chúng tôi sẽ sử dụng Python 3. 8. 10. Đi nào. ⚡⚡✨✨

Eratosthenes là một nhà toán học sống ở Hy Lạp cổ đại. Sàng của Eratosthenes là một thuật toán do ông phát triển cho phép chúng ta, ngay cả ngày nay, tìm một cách hiệu quả các số nguyên tố nhỏ hơn bất kỳ số nguyên n nào. Đây là mã của chúng tôi

def esieve[n]:
    multiples = []
    for i in range[2, n+1]:
        if i not in multiples:
            print[i]
            for j in range[i*i, n+1, i]:

                multiples.append[j]

esieve[17]

#Output
#2
#3
#5
#7
#11
#13
#17

Hãy giải thích những gì đang xảy ra ở đây

1. Chức năng của chúng tôi esieve[] là những gì sẽ thực sự thực hiện thuật toán Sàng của Eratosthenes. Nó nhận một đối số n và sẽ in ra tất cả các số nguyên tố nhỏ hơn hoặc bằng n. Đây là các bước
   • chúng tôi khai báo một danh sách mới bội số
   • chúng tôi tạo một danh sách các số nguyên từ 2 đến n+1
   • bắt đầu từ i=2, chúng tôi “đánh dấu” tất cả các bội số của i trong danh sách bằng cách chèn từng bội số vào bội số của danh sách, tối đa là n+1 Quảng cáo
   • mỗi khi kết thúc vòng lặp này ta kiểm tra xem i có nằm trong danh sách bội số không, nếu không là số nguyên tố và in ra màn hình
   • sau đó chúng ta tăng đến i=3 và chạy lại tất cả các số, mỗi lần chèn bội số của i vào bội số danh sách của chúng ta và kiểm tra xem sau khi hoàn thành vòng lặp, nó có nằm trong bội số của danh sách không
   • chúng tôi tiến hành bằng cách tăng i theo cách này và thực hiện việc “đánh dấu” này cho đến khi n+1 tại thời điểm đó quá trình hoàn tất và sàng đã hoàn thành công việc của nó
2. Chúng tôi đã sửa đổi sàng để bao gồm các số nguyên tố lên đến và bao gồm n

Đơn giản phải không? . Các giải pháp khác trông thanh lịch hơn nhưng chúng không thể đọc được

Tìm hiểu thêm về thuật toán này TẠI ĐÂY. Và xem hướng dẫn tuyệt vời khác của chúng tôi TẠI ĐÂY. Cảm ơn vì đã đọc. Chúc may mắn. 👌👌👌

Tìm số nguyên tố có tầm quan trọng đặc biệt đối với các ứng dụng thực tế như mật mã. Nhiều phương pháp khóa công khai chỉ an toàn theo quan điểm mật mã vì nó thường không hiệu quả và chậm để tính toán thừa số nguyên tố của các số lớn

Khi bạn xem qua bài viết, vui lòng xem video giải thích của tôi về Sàng Eratosthenes

https. //Nhanh. hoa tử đằng. mạng/nhúng/iframe/6uei6lyfym

Xây dựng vấn đề

Số nguyên tố n là một số nguyên không chia hết mà không có phần dư cho bất kỳ số [số nguyên] nào khác ngoài 1 và n. Nói cách khác, không tồn tại hai số nguyên a và b sao cho tích của chúng bằng số nguyên tố.

# Find all prime numbers