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. ⚡⚡✨✨
quảng cáoEratosthenes 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
- 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ó
- 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
quảng cáoTì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. 👌👌👌
Sàng của Eratosthenes là một thuật toán rất phổ biến để lấy
[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]
Thuật toán đơn giản dễ hiểu và thường được triển khai trong lập trình. Hướng dẫn này sẽ chứng minh việc triển khai thuật toán
[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 ta hãy bắt đầu bằng cách tìm hiểu logic đằng sau thuật toán này. Đầu tiên, chúng tôi viết tất cả các số
[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]
[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]
Sau đó, chúng tôi lấy số nguyên tố đầu tiên,
[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]
[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]
[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]
Quy trình tương tự được thực hiện cho đến số nguyên tố 7
[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]
[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]
Hình dưới đây minh họa kết quả cuối cùng
Sử dụng Sàng Eratosthenes trong Python
Trước tiên chúng tôi sẽ tạo một danh sách các phạm vi cần thiết. Danh sách này sẽ đánh dấu
[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]
[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]
Ban đầu, danh sách chứa tất cả các phần tử là True. Chúng tôi sẽ sử dụng một vòng lặp lồng nhau để thực hiện các thay đổi và đánh dấu các vị trí của
[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]
[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]
Sau này, chúng tôi sẽ lưu trữ các vị trí mà giá trị vẫn là True trong một danh sách mới. Danh sách này chứa các số nguyên tố
________số 8
đầu ra
[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]
Có thể thực hiện các thay đổi nhỏ đối với đoạn mã trên để cải thiện độ phức tạp về thời gian. Chẳng hạn, chúng ta có thể sử dụng bộ hoặc từ điển để lọc các số không nguyên tố
Kết quả cuối cùng được trả về trong một danh sách, nhưng hãy sử dụng từ điển hoặc bộ khi đánh dấu các số
[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]
[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]
[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]
[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]
[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]
đầu ra
[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]
Trong ví dụ trên, chúng tôi sử dụng từ điển
[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]
[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]
[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]