Chương trình Python Sieve of Eratosthenes (Sàng Eratosthenes)

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho số n, cần in tất cả số nguyên tố nhỏ hơn hoặc bằng n. Ràng buộc: n là số nhỏ.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

def SieveOfEratosthenes(n):
    # mảng boolean toàn True
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):
        # Nếu vẫn True -> nguyên tố
        if (prime[p] == True):
            # cập nhật bội số
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    prime[0] = False
    prime[1] = False
    # In
    for p in range(n + 1):
        if prime[p]:
            print(p, end=" ")

# main
if __name__ == '__main__':
    n = 33
    print("Các số nguyên tố <= ", n, " là:")
    SieveOfEratosthenes(n)

Kết quả

Các số nguyên tố <= 33 là: 2 3 5 7 11 13 17 19 23 29 31

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python Sieve of Eratosthenes.