Thuật toán Fermat, hay còn được gọi là thuật toán kiểm tra số nguyên tố Fermat, là một phương pháp đơn giản để kiểm tra tính nguyên tố của một số. Nó dựa trên định lý Fermat, được đề xuất bởi nhà toán học Pierre de Fermat.
Định lý Fermat nói rằng nếu p là một số nguyên tố và a là một số nguyên không chia hết cho p, thì:
a^(p-1) ≡ 1 (mod p)
Ở đây, a^(p-1) đại diện cho a mũ (p-1), và “mod” là phép chia lấy phần dư. Nếu một số không thỏa mãn điều kiện trên, tức là a^(p-1) không cùng với 1 (mod p), thì số đó không phải là số nguyên tố.
Thuật toán Fermat sử dụng định lý Fermat để kiểm tra tính nguyên tố của một số nguyên dương n. Cách thức của thuật toán như sau:
- Chọn một số nguyên dương a (thường là một số ngẫu nhiên) trong khoảng từ 2 đến n-1.
- Tính toán a^(n-1) mod n.
- Nếu a^(n-1) mod n không bằng 1, số n không phải là số nguyên tố.
- Lặp lại các bước trên với các giá trị a khác nhau để tăng độ chính xác của thuật toán. Nếu tất cả các lần tính toán đều trả về 1, thì số n có thể là số nguyên tố.
Tuy thuật toán Fermat đơn giản, nhưng nó không phải là phương pháp kiểm tra số nguyên tố chính xác nhất. Có một số số hợp số (không phải là số nguyên tố) có thể “đánh lừa” thuật toán này, gây ra lỗi sai dương (false positive). Do đó, trong thực tế, thuật toán Fermat thường được sử dụng như một phần của các phương pháp kiểm tra số nguyên tố phức tạp hơn như thuật toán Miller-Rabin để đảm bảo tính chính xác.
Dưới đây là một ví dụ cài đặt thuật toán Fermat trong Python:
import random
def power_mod(base, exponent, modulus):
# Tính toán (base^exponent) mod modulus
result = 1
while exponent > 0:
if exponent % 2 == 1:
result = (result * base) % modulus
base = (base * base) % modulus
exponent //= 2
return result
def is_prime_fermat(n, k=5):
# Kiểm tra tính nguyên tố của số n bằng thuật toán Fermat
if n <= 1:
return False
for _ in range(k):
a = random.randint(2, n - 1)
if power_mod(a, n - 1, n) != 1:
return False
return True
# Sử dụng hàm is_prime_fermat để kiểm tra tính nguyên tố của một số
number = 17
if is_prime_fermat(number):
print(number, "là số nguyên tố")
else:
print(number, "không phải là số nguyên tố")
Trong ví dụ trên, hàm power_mod được sử dụng để tính toán (base^exponent) mod modulus theo phương pháp lũy thừa nhân với lấy phần dư.
Hàm is_prime_fermat kiểm tra tính nguyên tố của số n bằng thuật toán Fermat. Tham số k là số lần lặp để tăng độ chính xác của thuật toán (mặc định là 5).
Cuối cùng, chúng ta sử dụng hàm is_prime_fermat để kiểm tra tính nguyên tố của số number và in kết quả tương ứng. Bạn có thể thay đổi giá trị của number để kiểm tra các số khác nhau.
Để tìm dãy số nguyên tố từ 1 đến n sử dụng thuật toán Fermat, bạn có thể sử dụng hàm is_prime_fermat trong một vòng lặp để kiểm tra tính nguyên tố của từng số trong khoảng. Dưới đây là một ví dụ:
import random
def power_mod(base, exponent, modulus):
# Tính toán (base^exponent) mod modulus
result = 1
while exponent > 0:
if exponent % 2 == 1:
result = (result * base) % modulus
base = (base * base) % modulus
exponent //= 2
return result
def is_prime_fermat(n, k=5):
# Kiểm tra tính nguyên tố của số n bằng thuật toán Fermat
if n <= 1:
return False
for _ in range(k):
a = random.randint(2, n - 1)
if power_mod(a, n - 1, n) != 1:
return False
return True
def find_prime_numbers(n):
prime_numbers = []
for num in range(2, n + 1):
if is_prime_fermat(num):
prime_numbers.append(num)
return prime_numbers
# Tìm dãy số nguyên tố từ 1 đến n
n = 100
prime_nums = find_prime_numbers(n)
print("Các số nguyên tố từ 1 đến", n, "là:", prime_nums)
Trong ví dụ trên, hàm find_prime_numbers sử dụng vòng lặp để kiểm tra tính nguyên tố của từng số từ 2 đến n bằng cách gọi hàm is_prime_fermat. Các số nguyên tố được tìm thấy được lưu trong danh sách prime_numbers.
Cuối cùng, chúng ta sử dụng hàm find_prime_numbers để tìm dãy số nguyên tố từ 1 đến n (trong ví dụ trên, n được đặt là 100) và in kết quả. Bạn có thể thay đổi giá trị của n để tìm các dãy số nguyên tố khác nhau.