Thuật toán sàng nguyên tố
Thuật toán sàng nguyên tố (Sieve of Eratosthenes) là một phương pháp đơn giản để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên n. Phương pháp này hoạt động bằng cách loại bỏ các số hợp số từ danh sách các số nguyên dương nhỏ hơn hoặc bằng n.
Để triển khai thuật toán sàng nguyên tố bằng Python, chúng ta có thể sử dụng một danh sách các số từ 2 đến n, sau đó loại bỏ các số hợp số bằng cách lặp lại các bước sau đến khi danh sách trở thành một danh sách các số nguyên tố:
-
Chọn số đầu tiên trong danh sách, nó sẽ là một số nguyên tố.
-
Loại bỏ tất cả các bội số của số đầu tiên đó khỏi danh sách.
-
Lặp lại bước 1 với số đầu tiên còn lại trong danh sách làm số nguyên tố tiếp theo.
Dưới đây là code Python triển khai thuật toán sàng nguyên tố:
def sieve_of_eratosthenes(n):
primes = []
sieve = [True] * (n+1)
for p in range(2, n+1):
if sieve[p]:
primes.append(p)
for i in range(p*p, n+1, p):
sieve[i] = False
return primes
Hàm sieve_of_eratosthenes(n) sẽ trả về danh sách các số nguyên tố nhỏ hơn hoặc bằng n. Đầu tiên, chúng ta khởi tạo một danh sách sieve gồm n+1 phần tử, mỗi phần tử ban đầu được đánh dấu là True.
Sau đó, chúng ta bắt đầu từ số đầu tiên là 2, đánh dấu số 2 là số nguyên tố và loại bỏ tất cả các bội số của 2 khỏi danh sách sieve. Tiếp theo, chúng ta chọn số đầu tiên còn lại trong danh sách sieve làm số nguyên tố tiếp theo và loại bỏ tất cả các bội số của nó khỏi danh sách sieve. Lặp lại quá trình này cho tới khi danh sách sieve chỉ còn các số nguyên tố.
Ví dụ. Liệt kê các số nguyên tố từ 1 đến n với sàng nguyên tố
Để liệt kê tất cả các số nguyên tố từ 1 đến n bằng thuật toán sàng nguyên tố, ta có thể sử dụng đoạn code sau đây trong Python:
def sieve_of_eratosthenes(n):
# Khởi tạo danh sách đánh dấu các số nguyên từ 2 đến n là True
primes = [True] * (n+1)
# Loại bỏ các số không phải là số nguyên tố bằng thuật toán sàng nguyên tố
for i in range(2, int(n**0.5)+1):
if primes[i]:
for j in range(i**2, n+1, i):
primes[j] = False
# Trả về danh sách các số nguyên tố từ 2 đến n
return [i for i in range(2, n+1) if primes[i]]
# Sử dụng hàm sieve_of_eratosthenes() để liệt kê các số nguyên tố từ 1 đến n
n = 100
primes = sieve_of_eratosthenes(n)
print(primes)
Trong đoạn code trên, hàm sieve_of_eratosthenes() sử dụng thuật toán sàng nguyên tố để tìm và lưu lại danh sách các số nguyên tố từ 2 đến n trong danh sách primes. Cuối cùng, chúng ta in danh sách các số nguyên tố này ra màn hình.
Lưu ý rằng trong thuật toán sàng nguyên tố, ta sử dụng danh sách primes để đánh dấu các số không phải là số nguyên tố bằng cách gán giá trị False cho chúng.
So sánh thuật toán sàng nguyên tố với thuật toán số nguyên tố thông thường
Trong lý thuyết số, thuật toán sàng nguyên tố được biết đến là phương pháp hiệu quả nhất để tìm tất cả các số nguyên tố trong một khoảng giá trị cho trước. So với phương pháp tìm số nguyên tố thông thường, thuật toán sàng nguyên tố có độ phức tạp thời gian tốt hơn.
Thuật toán tìm số nguyên tố thông thường có thể được viết như sau:
def is_prime(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
Trong đó, hàm is_prime() nhận vào một số nguyên n và trả về True nếu n là số nguyên tố và False nếu không phải.
Độ phức tạp của thuật toán tìm số nguyên tố thông thường là O(n), vì trong trường hợp tệ nhất, chúng ta phải kiểm tra tất cả các số từ 2 đến n-1 để xác định xem n có phải là số nguyên tố hay không.
Trong khi đó, thuật toán sàng nguyên tố có độ phức tạp thời gian là O(n log(log n)). Điều này được giải thích bởi việc thuật toán sàng nguyên tố sẽ lặp lại từng số nguyên trong khoảng từ 2 đến n, và loại bỏ tất cả các bội số của từng số nguyên này. Số lượng bội số cần phải được loại bỏ là log-logarithmic với n.
Vì vậy, trong trường hợp chúng ta cần tìm tất cả các số nguyên tố trong một khoảng giá trị cho trước, thuật toán sàng nguyên tố sẽ hiệu quả hơn nhiều so với thuật toán tìm số nguyên tố thông thường.
Khi nào cần dùng đến sàng nguyên tố?
Khi cần tìm tất cả các số nguyên tố trong một khoảng giá trị cho trước thì nên sử dụng thuật toán sàng nguyên tố. Vì độ phức tạp của thuật toán sàng nguyên tố là tối ưu hơn so với thuật toán tìm số nguyên tố thông thường trong trường hợp này.
Tuy nhiên, trong trường hợp cần kiểm tra một số nguyên bất kỳ có phải là số nguyên tố hay không, thì thuật toán tìm số nguyên tố thông thường là phương pháp tốt hơn, vì trong trường hợp này ta không biết trước giới hạn của các số cần kiểm tra. Vì vậy, thuật toán tìm số nguyên tố thông thường là phương pháp linh hoạt hơn trong trường hợp cần kiểm tra một số nguyên bất kỳ có phải là số nguyên tố hay không.
Tóm lại, nếu cần tìm tất cả các số nguyên tố trong một khoảng giá trị cho trước, ta nên sử dụng thuật toán sàng nguyên tố, và nếu cần kiểm tra tính nguyên tố của một số nguyên bất kỳ, ta nên sử dụng thuật toán tìm số nguyên tố thông thường.