Sàng số nguyên tố (Sàng Eratosthenes) – O₂ Education

Posted on by mtoplistChuyên mục:Top List

Sàng số nguyên tố (Sàng Eratosthenes)

Bài toán liệt kê các số nguyên tố nhỏ hơn số n cho trước là một bài toán quan trọng trong Toán học và Tin học.

SALE 11.11

Phương pháp đơn giản nhất là chúng ta duyệt qua các số tự nhiên nhỏ hơn n, và lần lượt kiểm tra tính nguyên tố của từng số này. Tuy nhiên, việc kiểm tra tính nguyên tố của một số tự nhiên n có độ phức tạp là $O(\sqrt{n})$, do đó duyệt qua n số này sẽ có độ phức tạp $O(\sqrt{1}+\sqrt{2}+\sqrt{3}+…+\sqrt{n})$.

Cách làm dưới đây sẽ giúp giảm độ phức tạp của chương trình đi rất nhiều.

SALE 11.11

Sàng Eratosthenes là gì?

Sàng Eratosthenes là một thuật giải toán cổ xưa để tìm các số nguyên tố nhỏ hơn 100. Thuật toán này do nhà toán học cổ Hy Lạp là Eratosthenes (Ơ-ra-tô-xten) “phát minh” ra.

Ban đầu, nhà toán học Eratosthenes sau khi tìm ra thuật toán, đã lấy lá cọ và ghi tất cả các số từ 2 cho đến 100. Ông đã chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes.

SALE 11.11

Bạn có thể xem trong hình dưới đây, các số tô màu giống nhau là bội của nhau số cùng màu nhưng được tô đậm hơn.

sàng số nguyên tố Sàng Eratosthenes

SALE 11.11

Thuật toán sàng số nguyên tố

Để tìm các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên N bằng sàng Eratosthenes, ta làm như sau:

  • Bước 1: Tạo 1 danh sách (List trong Python, Dart hoặc array trong C)các số tự nhiên liên tiếp từ 2 đến n: [2, 3, 4,..., n].
  • Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p = 2 là số nguyên tố đầu tiên.
  • Bước 3: Tất cả các bội số của p: 2p, 3p, 4p,… sẽ bị đánh dấu vì không phải là số nguyên tố.
  • Bước 4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p và nhỏ hơn hoặc bằng căn bậc 2 của n . Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.

Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm.

SALE 11.11

Thay vì phải đánh dấu, chúng ta có thể xóa phần tử không là số nguyên tố của danh sách thì cuối cùng sẽ còn lại là các số nguyên tố.

Mời bạn tham khảo mã nguồn chương trình bằng Python:

SALE 11.11 

def SieveOfEratosthenes(n):
   
   # Create a boolean array "prime[0..n]" and initialize
   # all entries it as true. A value in prime[i] will
   # finally be false if i is Not a prime, else true.
   prime = [True for i in range(n + 1)]
   p = 2
   while (p * p <= n):
      
      # If prime[p] is not changed, then it is a prime
      if (prime[p] == True):
         
         # Update all multiples of p
         for i in range(p ** 2, n + 1, p):
            prime[i] = False
      p += 1
   prime[0]= False
   prime[1]= False
   # Print all prime numbers
   for p in range(n + 1):
      if prime[p]:
         print(p)
if __name__=='__main__':
   n = 30
   print("Following are the prime numbers smaller than or equal to", n)
   SieveOfEratosthenes(n)

mtoplist