NỘI DUNG
Số nguyên tố là những số nguyên dương chỉ có 2 ước là 1 và chính nó. Chính vì sự đặc biệt đó mà nhiều bài toán lập trình đề cập đến loại số nguyên đặc biệt này trong các đề thi học sinh giỏi môn Tin học các cấp. Có nhiều thuật toán khác nhau để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên đã cho. Dưới đây là một số trong những thuật toán phổ biến để giải quyết bài toán này:
Sàng Eratosthenes
Đây là một trong những thuật toán cổ điển và hiệu quả nhất để tìm tất cả các số nguyên tố trong một khoảng cho trước. Thuật toán hoạt động bằng cách loại bỏ tất cả các bội số của các số nguyên tố đã biết từ danh sách các số nguyên.
def sieve_eratosthenes(n):
prime = [True] * (n+1)
p = 2
while p**2 <= n:
if prime[p]:
for i in range(p**2, n+1, p):
prime[i] = False
p += 1
primes = [p for p in range(2, n+1) if prime[p]]
return primes
n = 50
print(sieve_eratosthenes(n))
Kiểm tra từng số một
Bạn có thể kiểm tra từng số trong khoảng cho trước xem nó có phải là số nguyên tố hay không. Đây không phải là cách hiệu quả nhất, nhất là cho các khoảng lớn, nhưng nó là một cách tiếp cận đơn giản và dễ hiểu.
def is_prime(num):
if num <= 1:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True
n = 50
primes = [i for i in range(2, n+1) if is_prime(i)]
print(primes)
Sử dụng thư viện và hàm sẵn có (thư viện sympy)
Nhiều ngôn ngữ lập trình đã tích hợp các hàm và thư viện để tìm số nguyên tố. Trong Python, bạn có thể sử dụng hàm sympy.primerange() để tìm tất cả các số nguyên tố trong một khoảng cụ thể.
import sympy
n = 50
primes = list(sympy.primerange(2, n+1))
print(primes)
Sàng Sundaram
Thuật toán Sàng Sundaram, còn được gọi là “Sàng Sundaram” hoặc “Sàng của Sundaram,” là một thuật toán toán học được đặt tên theo nhà toán học người Ấn Độ K. S. Sàng Sundaram. Thuật toán này được sử dụng để tạo ra một danh sách các số nguyên tố nhỏ hơn một số nguyên dương cho trước, thường được ký hiệu là “n.”
Dưới đây là các bước cụ thể để thực hiện thuật toán Sàng Sundaram để tạo ra danh sách các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương n cho trước:
- Khởi tạo một mảng gốc chứa các số từ 1 đến n (bao gồm cả n). Đây sẽ là mảng ban đầu mà bạn sẽ thực hiện thuật toán.
- Loại bỏ các phần tử có dạng i + j + 2ij khỏi mảng, với i, j là các số nguyên dương và 1 ≤ i ≤ j sao cho i + j + 2ij không vượt quá n. Trong quá trình này, bạn sẽ duyệt qua tất cả các cặp số (i, j) và loại bỏ phần tử tương ứng khỏi mảng.
- Duyệt qua tất cả các i từ 1 đến n/2.
- Duyệt qua tất cả các j từ i đến (n – i) / (2i + 1).
- Tại mỗi bước, tính giá trị k = i + j + 2ij và đánh dấu k trong mảng là đã bị loại bỏ bằng cách gán mảng[k] = false.
- Sau khi hoàn thành quá trình loại bỏ, các phần tử còn lại trong mảng chính là danh sách các số nguyên tố nhỏ hơn hoặc bằng n.
Lưu ý rằng thuật toán này chỉ loại bỏ các số nguyên tố chẵn trừ số 2 (vì 2 không thể biểu diễn dưới dạng 2i + 1 với i là số nguyên dương), nên bạn thường sẽ bổ sung số 2 vào danh sách số nguyên tố nếu nó không nằm trong mảng kết quả ban đầu.
def sieve_sundaram(n):
# Tạo mảng chứa các số từ 1 đến n
numbers = list(range(1, n + 1))
# Sàng Sundaram
for i in range(1, n // 2 + 1):
for j in range(i, (n - i) // (2 * i + 1) + 1):
k = i + j + 2 * i * j
if k <= n:
numbers[k - 1] = 0 # Loại bỏ phần tử khỏi danh sách bằng cách đặt giá trị thành 0
# Loại bỏ số 1 khỏi danh sách (nếu có)
numbers = [x for x in numbers if x != 0]
# Bổ sung số 2 vào danh sách nếu nó không có trong đó
if 2 not in numbers:
numbers.insert(0, 2)
return numbers
n = 50
prime_numbers = sieve_sundaram(n)
print(prime_numbers)
Sử dụng thuật toán Miller-Rabin
Đây là một thuật toán kiểm tra số nguyên tố ngẫu nhiên, thường được sử dụng khi cần kiểm tra số nguyên tố một cách nhanh chóng cho các số lớn.
import random # tạo số nguyên ngẫu nhiên
import sympy # thư viện này chứa nhiều chức năng liên quan đến số nguyên tố
# Hàm kiểm tra số nguyên tố bằng thuật toán Miller-Rabin
def la_so_nguyen_to_miller_rabin(num, k=5):
if num <= 1:
return False # Nếu số num nhỏ hơn hoặc bằng 1, nó không phải là số nguyên tố
if num == 2 or num == 3:
return True # Nếu num bằng 2 hoặc 3, nó là số nguyên tố
if num % 2 == 0:
return False # không phải là số nguyên tố
# Đây là hàm con trong hàm trên thực hiện kiểm tra Miller-Rabin cho một lần kiểm tra cụ thể.
def kiem_tra_miller_rabin(num, d, r):
a = random.randint(2, num - 2)
x = pow(a, d, num)
if x == 1 or x == num - 1:
return True
for _ in range(r - 1):
x = (x * x) % num
if x == num - 1:
return True
return False
d = num - 1
r = 0
while d % 2 == 0:
d //= 2
r += 1
for _ in range(k):
if not kiem_tra_miller_rabin(num, d, r):
return False
return True
n = 50
so_nguyen_to = [i for i in range(2, n+1) if la_so_nguyen_to_miller_rabin(i)]
print(so_nguyen_to)
Đánh giá độ phức tạp của các thuật toán
Trên đây là các thuật toán xử lý bài toán: Tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên đã cho. Chúng ta thấy: Tính tối ưu của một thuật toán để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên đã cho phụ thuộc vào nhiều yếu tố như kích thước của số, hiệu năng của máy tính, và ngôn ngữ lập trình. Dưới đây là một số yếu tố cần xem xét:
- Tốc độ thực thi: Sàng Eratosthenes và Sàng Sundaram thường nhanh hơn so với việc kiểm tra từng số một hoặc sử dụng thuật toán Miller-Rabin để các số lớn. Sàng Eratosthenes thường nhanh hơn trong các trường hợp lớn.
- Sự dễ dàng triển khai: Kiểm tra từng số một và sử dụng thuật toán Miller-Rabin có thể dễ dàng triển khai và hiểu, trong khi Sàng Eratosthenes và Sàng Sundaram có thể phức tạp hơn.
- Khả năng xử lý số lớn: Sàng Eratosthenes và Sàng Sundaram có thể cần nhiều bộ nhớ hơn để xử lý các khoảng số lớn, trong khi kiểm tra từng số một và thuật toán Miller-Rabin có thể linh hoạt hơn với các số lớn.
Tóm lại, Sàng Eratosthenes thường được xem là thuật toán tốt nhất để tìm tất cả các số nguyên tố trong một khoảng cho trước trong hầu hết các trường hợp, đặc biệt là với các số nhỏ. Tuy nhiên, với các số rất lớn, việc sử dụng thuật toán Miller-Rabin hoặc kiểm tra từng số một có thể trở thành lựa chọn tốt hơn vì họ cung cấp khả năng linh hoạt và khả năng xử lý số lớn hơn.