NỘI DUNG
Giới thiệu bài toán
Số Mersenne là các số nguyên tố dạng 2^p – 1, trong đó p là số nguyên tố. Bài toán yêu cầu tìm các số Mersenne từ 1 đến n.
Các bước thực hiện thuật toán
- Lặp qua các số nguyên tố p từ 2 đến sqrt(n).
- Tính 2^p – 1 và kiểm tra xem kết quả có phải là số nguyên tố hay không.
- Nếu kết quả là số nguyên tố, thì đó là số Mersenne và được đưa vào danh sách kết quả.
Ví dụ về thuật toán: Giả sử n = 31.
- Với p = 2, ta có 2^2 – 1 = 3, là số nguyên tố. Do đó, 3 là số Mersenne.
- Với p = 3, ta có 2^3 – 1 = 7, là số nguyên tố. Do đó, 7 là số Mersenne.
- Với p = 5, ta có 2^5 – 1 = 31, là số nguyên tố. Do đó, 31 là số Mersenne. Vậy các số Mersenne từ 1 đến 31 là: 3, 7, 31.
Cài đặt thuật toán với Python
import math
def is_prime(n):
if n < 2:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
def find_mersenne_numbers(n):
mersenne_numbers = []
for p in range(2, int(math.sqrt(n)) + 1):
mersenne_number = 2**p - 1
if is_prime(mersenne_number):
mersenne_numbers.append(mersenne_number)
return mersenne_numbers
Đánh giá độ phức tạp
- Độ phức tạp thời gian của thuật toán là O(sqrt(n) * log n), vì ta lặp qua các số nguyên tố p từ 2 đến sqrt(n), và tính 2^p – 1 trong log n thao tác.
- Độ phức tạp không gian của thuật toán là O(sqrt(n)), vì ta lưu trữ danh sách các số Mersenne tìm được.
Tối ưu hóa thuật toán
Thuật toán tối ưu hơn để tìm các số Mersenne là thuật toán Lucas-Lehmer. Thuật toán này chỉ kiểm tra tính nguyên tố của các số Mersenne, không cần kiểm tra tính nguyên tố của các số khác.
Các bước thực hiện thuật toán
Thuật toán Lucas-Lehmer hoạt động như sau:
- Bắt đầu với số Mersenne đầu tiên: M1 = 3.
- Với mỗi số Mersenne tiếp theo, Mi = 2^Pi – 1, tính giá trị của số nguyên S, bắt đầu với S = 4.
- Lặp lại (Pi – 2) lần: S = ((S * S) – 2) mod Mi.
- Nếu S = 0 thì Mi là số nguyên tố, nếu không thì Mi không phải là số nguyên tố.
Ví dụ về thuật toán
Giả sử chúng ta muốn tìm số Mersenne thứ 4, M4 = 2^4 – 1 = 15. Ta áp dụng thuật toán Lucas-Lehmer:
- Bắt đầu với số Mersenne đầu tiên, M1 = 3.
- Với M2 = 2^2 – 1 = 3, ta tính S = 4. Do P2 – 2 = 0, nên ta kết luận M2 = 3 là số nguyên tố.
- Với M3 = 2^3 – 1 = 7, ta tính S = 4^2 – 2 mod 7 = 2. Vì P3 – 2 = 1, nên ta lặp lại thêm một lần nữa: S = 2^2 – 2 mod 7 = 2. Do đó, M3 = 7 là số nguyên tố.
- Với M4 = 2^4 – 1 = 15, ta tính S = 4^2 – 2 mod 15 = 6. Do P4 – 2 = 2, nên ta lặp lại thêm hai lần nữa: S = 6^2 – 2 mod 15 = 11, và S = 11^2 – 2 mod 15 = 1. Do S = 0, nên M4 = 15 là số nguyên tố.
Cài đặt thuật toán Lucas-Lehmer với Python:
Cài đặt thuật toán với Python
Dưới đây là một phiên bản của thuật toán Lucas-Lehmer được cài đặt bằng Python:
def lucas_lehmer(p):
s = 4
m = 2**p - 1
for i in range(p - 2):
s = ((s * s) - 2) % m
return s == 0
def find_mersenne_numbers(n):
mersenne_numbers = []
for p in range(2, n + 1):
mersenne_number = 2**p - 1
if lucas_lehmer(p):
mersenne_numbers.append(mersenne_number)
return
Đánh giá độ phức tạp của thuật toán
Độ phức tạp của thuật toán Lucas-Lehmer để kiểm tra tính nguyên tố của một số Mersenne M_p là O(p^2), trong đó p là số mũ của số Mersenne. Vì vậy, độ phức tạp của thuật toán tìm các số Mersenne trong khoảng từ 1 đến n là O(n^2 log n).
Tuy nhiên, thuật toán Lucas-Lehmer vẫn nhanh hơn thuật toán đơn giản hơn được trình bày trước đó vì nó chỉ cần kiểm tra tính nguyên tố của các số Mersenne thay vì kiểm tra tính nguyên tố của tất cả các số trong khoảng từ 1 đến n. Nếu n lớn, thì tốc độ thực thi của thuật toán Lucas-Lehmer sẽ nhanh hơn đáng kể so với thuật toán đơn giản hơn.
Độ phức tạp của thuật toán tìm các số Mersenne bằng cách kiểm tra tính nguyên tố của tất cả các số trong khoảng từ 1 đến n là O(n^2), trong khi đó độ phức tạp của thuật toán Lucas-Lehmer là O(n^2 log n). Vì vậy, thuật toán Lucas-Lehmer có độ phức tạp lớn hơn so với thuật toán đơn giản hơn khi n tăng lên. Tuy nhiên, trong thực tế, thuật toán Lucas-Lehmer vẫn nhanh hơn do nó chỉ kiểm tra tính nguyên tố của các số Mersenne thay vì kiểm tra tính nguyên tố của tất cả các số trong khoảng từ 1 đến n. Nếu n lớn, thì tốc độ thực thi của thuật toán Lucas-Lehmer sẽ nhanh hơn đáng kể so với thuật toán đơn giản hơn. Vì vậy, thuật toán Lucas-Lehmer được coi là thuật toán tối ưu hơn để tìm các số Mersenne./.