Bài 16.2. Thuật toán Sieve of Eratosthenes với Python

Chào mừng các bạn đến với một thuật toán cổ điển nhưng vô cùng thanh lịch và hiệu quả để giải quyết một bài toán quen thuộc: tìm tất cả các số nguyên tố nhỏ hơn một số N cho trước. Đó chính là Thuật toán Sieve of Eratosthenes, hay còn gọi là Sàng Eratosthenes.

Số nguyên tố luôn có một sức hấp dẫn đặc biệt trong toán học và khoa học máy tính. Việc tìm ra chúng một cách nhanh chóng là chìa khóa cho nhiều ứng dụng. Hãy cùng vén bức màn bí ẩn của thuật toán huyền thoại này và xem cách Python giúp chúng ta triển khai nó nhé!

Thuật toán Sàng Eratosthenes là gì?

Ý tưởng cốt lõi của Sàng Eratosthenes rất trực quan:

Bắt đầu với một danh sách tất cả các số tự nhiên từ 2 đến N.
Giả sử tất cả chúng ban đầu đều là số nguyên tố.
Tìm số nguyên tố đầu tiên (là số 2).
Loại bỏ (hay "sàng lọc") tất cả các bội của số nguyên tố đó (4, 6, 8, ...) ra khỏi danh sách vì chúng chắc chắn không phải là số nguyên tố.
Tìm số tiếp theo trong danh sách chưa bị loại bỏ (là số 3). Đây là số nguyên tố tiếp theo.
Lặp lại quá trình sàng lọc: loại bỏ tất cả các bội của số nguyên tố mới tìm được (6, 9, 12, ...).
Tiếp tục quá trình này cho đến khi bạn đã xét hết các số nguyên tố cần thiết.
Những số còn lại trong danh sách chính là các số nguyên tố nhỏ hơn hoặc bằng N.

Nghe giống như bạn đang dùng một cái sàng để giữ lại những viên đá quý (số nguyên tố) và loại bỏ đi sỏi đá (hợp số) phải không?

Các Bước Thực Hiện Chi Tiết

Tạo một danh sách boolean is_prime có kích thước N+1. Khởi tạo tất cả các giá trị là True. is_prime[i] sẽ cho biết số i có phải là số nguyên tố hay không.
Đánh dấu is_prime[0] và is_prime[1] là False vì 0 và 1 không phải số nguyên tố.
Bắt đầu với số nguyên tố đầu tiên p = 2.
Trong khi p * p <= N:
- Nếu is_prime[p] là True (nghĩa là p là số nguyên tố):
  - Đánh dấu tất cả các bội của p từ p*p đến N là False. Chúng ta bắt đầu từ p*p vì các bội nhỏ hơn (như 2*p, 3*p) đã bị đánh dấu bởi các số nguyên tố nhỏ hơn p rồi. Bước nhảy là p.
  - Ví dụ: với p=2, đánh dấu 4, 6, 8,...; với p=3, đánh dấu 9, 12, 15,...
- Tăng p lên 1 để xét số tiếp theo.
Sau khi vòng lặp kết thúc, duyệt qua danh sách is_prime. Nếu is_prime[i] là True, thì i là số nguyên tố.

Minh họa với N = 10:

Khởi tạo: [F, F, T, T, T, T, T, T, T, T, T] (indices 0-10)
p = 2: is_prime[2] là T. Đánh dấu bội từ 2*2=4: 4, 6, 8, 10 là F.
- [F, F, T, T, F, T, F, T, F, T, F]
p = 3: is_prime[3] là T. Đánh dấu bội từ 3*3=9: 9 là F.
- [F, F, T, T, F, T, F, T, F, F, F]
p = 4: p*p = 16 > 10. Dừng vòng lặp.
Kết quả: Các số i mà is_prime[i] là True: 2, 3, 5, 7.

Triển Khai Bằng Python

Đây là cách bạn có thể viết hàm Sieve of Eratosthenes trong Python:

import math # Cần thiết cho việc tính căn bậc hai nếu tối ưu, nhưng không bắt buộc cho logic cơ bản

def sieve_of_eratosthenes(n):
  """
  Tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng n bằng thuật toán Sieve of Eratosthenes.

  Args:
    n: Giới hạn trên (số nguyên dương).

  Returns:
    Một list chứa tất cả các số nguyên tố từ 2 đến n.
  """
  if n < 2:
    return [] # Không có số nguyên tố nào nhỏ hơn 2

  # 1. Tạo danh sách boolean, ban đầu tất cả là True
  is_prime = [True] * (n + 1)

  # 2. Đánh dấu 0 và 1 không phải số nguyên tố
  is_prime[0] = is_prime[1] = False

  # 3. Bắt đầu sàng lọc từ p = 2
  p = 2
  # 4. Vòng lặp chỉ cần chạy đến căn bậc hai của n (p*p <= n)
  while (p * p <= n):
    # Nếu is_prime[p] chưa bị đánh dấu False, thì p là số nguyên tố
    if (is_prime[p] == True):
      # Đánh dấu tất cả các bội của p là False
      # Bắt đầu từ p*p, bước nhảy là p
      for i in range(p * p, n + 1, p):
        is_prime[i] = False
    p += 1 # Chuyển sang số tiếp theo để kiểm tra

  # 5. Thu thập tất cả các số nguyên tố
  primes = []
  for i in range(n + 1):
    if is_prime[i]:
      primes.append(i)

  return primes

Giải Thích Code

if n < 2: return []: Xử lý trường hợp đầu vào không hợp lệ hoặc không có số nguyên tố nào.
is_prime = [True] * (n + 1): Tạo một list boolean is_prime với n+1 phần tử (từ index 0 đến n). Ban đầu, chúng ta giả định tất cả các số đều là số nguyên tố (True).
is_prime[0] = is_prime[1] = False: Đánh dấu số 0 và 1 là không phải số nguyên tố theo định nghĩa.
p = 2: Bắt đầu kiểm tra từ số nguyên tố nhỏ nhất.
while (p * p <= n):: Vòng lặp chính chỉ cần chạy đến khi p*p vượt quá n. Như đã giải thích, nếu một số m <= n là hợp số và có thừa số p > sqrt(n), thì nó phải có một thừa số khác q < sqrt(n), và m đã bị loại bỏ khi xét đến q.
if (is_prime[p] == True):: Chỉ thực hiện sàng lọc nếu p hiện tại được xác định là số nguyên tố (chưa bị đánh dấu False bởi một số nguyên tố nhỏ hơn).
for i in range(p * p, n + 1, p): is_prime[i] = False: Đây là bước "sàng". Vòng lặp này đi qua tất cả các bội của p (bắt đầu từ p*p, với bước nhảy là p) và đánh dấu chúng là False (không phải số nguyên tố).
p += 1: Di chuyển đến số tiếp theo để kiểm tra trong vòng lặp while.
primes = [] ... for ... if is_prime[i]: primes.append(i): Sau khi quá trình sàng lọc hoàn tất, tạo một list rỗng primes và duyệt qua is_prime. Nếu is_prime[i] vẫn là True, thì i là số nguyên tố, thêm nó vào list primes.
return primes: Trả về danh sách các số nguyên tố tìm được.

Ví Dụ Minh Họa

Ví dụ 1: Tìm số nguyên tố nhỏ hơn hoặc bằng 30

primes_up_to_30 = sieve_of_eratosthenes(30)
print(f"Các số nguyên tố <= 30 là: {primes_up_to_30}")
# Kết quả: Các số nguyên tố <= 30 là: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Ví dụ 2: Tìm số nguyên tố nhỏ hơn hoặc bằng 100

primes_up_to_100 = sieve_of_eratosthenes(100)
print(f"Các số nguyên tố <= 100 là: {primes_up_to_100}")
print(f"Có tổng cộng {len(primes_up_to_100)} số nguyên tố <= 100.")
# Kết quả:
# Các số nguyên tố <= 100 là: [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ó tổng cộng 25 số nguyên tố <= 100.

Tại Sao Thuật Toán Này Hiệu Quả?

Sàng Eratosthenes có độ phức tạp thời gian xấp xỉ $O(n \log \log n)$, nhanh hơn đáng kể so với việc kiểm tra tính nguyên tố của từng số từ 1 đến n bằng phép chia thử (có độ phức tạp khoảng $O(n \sqrt{n})$). Lý do chính là nó tránh được việc kiểm tra lặp đi lặp lại. Mỗi hợp số chỉ bị "sàng" (đánh dấu False) bởi các thừa số nguyên tố của nó, và thường là bởi thừa số nguyên tố nhỏ nhất.

Kết Luận

Sieve of Eratosthenes là một minh chứng tuyệt vời cho sự thanh lịch và sức mạnh của các thuật toán cổ điển. Dù đã có từ hàng ngàn năm trước, nó vẫn là một trong những phương pháp hiệu quả nhất để tìm tất cả các số nguyên tố trong một phạm vi nhất định. Việc triển khai nó trong Python khá đơn giản và trực quan, cho thấy sự linh hoạt của ngôn ngữ này trong việc giải quyết các bài toán toán học.

Hãy thử nghiệm với thuật toán này, thay đổi giá trị n và xem nó hoạt động nhanh như thế nào nhé!

#HappyCoding cùng FullhouseDev! 🚀

Comments

There are no comments at the moment.