Thuật toán sử dụng sàng Eratosthenes trong Python

Sàng Eratosthenes là một thuật toán cổ điển được sử dụng để tạo danh sách các số nguyên tố trong một khoảng cố định từ 2 đến n. Thuật toán này được đặt tên theo Eratosthenes, một nhà toán học cổ đại người Hy Lạp, người đã phát minh ra phương pháp này vào thế kỷ 3 trước Công nguyên.

Sàng Eratosthenes hoạt động như sau:

Bắt đầu với một danh sách gồm tất cả các số từ 2 đến n. Ban đầu, tất cả các số đều được xem xét là số nguyên tố.
Bắt đầu từ số nguyên tố đầu tiên trong danh sách, tức là số 2, đánh dấu tất cả các bội số của nó (2, 4, 6, 8, v.v.) là không phải là số nguyên tố. Điều này được thực hiện bằng cách đặt giá trị của các bội số này trong danh sách thành False.
Tiếp tục với số nguyên tố tiếp theo chưa bị đánh dấu là không phải là số nguyên tố và lặp lại bước 2 cho đến khi bạn đã xem xét tất cả các số trong danh sách.
Sau khi hoàn thành bước 3, các số còn lại trong danh sách sẽ là các số nguyên tố. Danh sách này là danh sách các số nguyên tố trong khoảng từ 2 đến n.

Sàng Eratosthenes rất hiệu quả vì nó loại bỏ tất cả các bội số của các số nguyên tố khi chúng ta đi qua danh sách các số nguyên tố. Thuật toán này thường được sử dụng để tìm tất cả các số nguyên tố trong khoảng cố định và là một công cụ quan trọng trong lĩnh vực số học và trong lập trình khi cần tìm số nguyên tố.

Bài toán: Liệt kê các số nguyên tố từ 1 đến n

Thuật toán:

Bước 1: Chúng ta tạo một danh sách is_prime để theo dõi trạng thái số nguyên tố từ 2 đến n. Ban đầu, chúng ta đánh dấu tất cả số là True (tức là là số nguyên tố), nhưng 0 và 1 không phải là số nguyên tố, nên chúng ta đặt is_prime[0] và is_prime[1] là False.
Bước 2: Chúng ta bắt đầu với số nguyên tố đầu tiên là 2.
Bước 3: Chúng ta lặp qua các số nguyên tố từ 2 đến căn bậc hai của n. Điều này đủ để loại bỏ các số nguyên tố không cần thiết.
Bước 4: Đánh dấu tất cả các bội số của số nguyên tố p là False trong danh sách is_prime. Chúng ta bắt đầu từ p^2 vì tất cả các bội số của p nhỏ hơn p^2 đã được đánh dấu bởi các số nguyên tố nhỏ hơn.
Bước 5: Chúng ta tạo danh sách primes chứa tất cả các số nguyên tố từ 2 đến n bằng cách lọc các giá trị là True trong danh sách is_prime.
Bước 6: Cuối cùng, chúng ta in dãy số nguyên tố từ 1 đến n sử dụng danh sách primes.

Dưới đây là mã Python để tìm dãy số nguyên tố từ 1 đến n:

def sieve_of_eratosthenes(n):
    # Bước 1: Tạo một danh sách để theo dõi các số nguyên tố từ 2 đến n
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0 và 1 không phải là số nguyên tố
    
    p = 2  # Bước 2: Bắt đầu với số nguyên tố đầu tiên là 2
    while p**2 <= n:  # Bước 3: Lặp qua các số nguyên tố từ 2 đến căn bậc hai của n
        if is_prime[p]:
            # Bước 4: Đánh dấu tất cả các bội số của số nguyên tố p là False
            for i in range(p**2, n + 1, p):
                is_prime[i] = False
        p += 1  # Chuyển sang số nguyên tố tiếp theo

    # Bước 5: Tạo danh sách chứa tất cả các số nguyên tố từ 2 đến n
    primes = [i for i in range(2, n + 1) if is_prime[i]]
    return primes

n = 50  # Thay đổi giá trị n theo nhu cầu của bạn
prime_sequence = sieve_of_eratosthenes(n)

# Bước 6: In dãy số nguyên tố từ 1 đến n
print("Dãy số nguyên tố từ 1 đến", n, "là:", prime_sequence)

Lập trình Python

Thuật toán sử dụng sàng Eratosthenes trong Python

Trả lời Hủy