Các thuật toán về Số nguyên tố với Python

NỘI DUNG

Định nghĩa số nguyên tố

Số nguyên tố là một số tự nhiên lớn hơn 1 và chỉ có hai ước số dương phân biệt là 1 và chính nó. Nghĩa là số nguyên tố không thể phân tích được thành tích của hai số tự nhiên dương khác nhau. Ví dụ: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,… là các số nguyên tố.

Các tính chất về số nguyên tố

Dưới đây là một số tính chất của số nguyên tố:

Mỗi số tự nhiên lớn hơn 1 đều có thể phân tích duy nhất thành tích các số nguyên tố (được gọi là tính chất phân tích duy nhất).
Một số tự nhiên là số nguyên tố khi và chỉ khi nó không chia hết cho bất kỳ số nguyên tố nào nhỏ hơn nó.
Số nguyên tố lớn nhất có thể là số nguyên tố lẻ hay số nguyên tố chẵn là 2.
Một số tự nhiên là số nguyên tố khi và chỉ khi nó có thể được biểu diễn dưới dạng 6k ± 1 (trừ 2 và 3).
Tổng các số nguyên tố từ 2 đến n là S(n) = 2 + 3 + 5 + … + p(n), trong đó p(n) là số nguyên tố thứ n.

Những tính chất trên đều rất hữu ích khi sử dụng trong các thuật toán và ứng dụng của số nguyên tố.

Các thuật toán về số nguyên tố

Phương pháp đơn giản: kiểm tra từng số

Phương pháp kiểm tra từng số là phương pháp đơn giản nhất để kiểm tra một số có phải là số nguyên tố hay không. Phương pháp này đơn giản là kiểm tra xem số cần kiểm tra có chia hết cho bất kỳ số nguyên tố nào nhỏ hơn nó hay không. Nếu không chia hết cho bất kỳ số nguyên tố nào, thì số đó là số nguyên tố.

Tuy nhiên, phương pháp này không phải là phương pháp hiệu quả để kiểm tra các số lớn. Nếu số cần kiểm tra là một số lớn, phương pháp này sẽ mất rất nhiều thời gian để kiểm tra từng số.

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

Sàng Eratosthenes

Sàng Eratosthenes là một thuật toán tìm số nguyên tố rất hiệu quả. Thuật toán này được đặt theo tên của nhà toán học Hy Lạp cổ đại Eratosthenes, người đã phát minh ra nó khoảng 200 trước Công nguyên.

Ý tưởng chính của thuật toán Sàng Eratosthenes là loại bỏ tất cả các bội số của các số nguyên tố khác nhau trong khoảng từ 2 đến một giới hạn nào đó, ví dụ như 100 hoặc 1000. Các số còn lại trong khoảng đó sẽ là số nguyên tố.

Cụ thể, ta bắt đầu với danh sách gồm các số từ 2 đến giới hạn cần tìm. Sau đó, ta lần lượt loại bỏ các bội số của từng số nguyên tố trong danh sách đó. Quá trình này sẽ kết thúc khi ta đã loại bỏ các bội số của tất cả các số nguyên tố trong danh sách.

def sieve_of_eratosthenes(n):
    # Tạo một danh sách chứa tất cả các số từ 2 đến n
    primes = [True] * (n+1)
    primes[0] = primes[1] = False

    # Loại bỏ các bội số của các số nguyên tố khác nhau
    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ố
    return [i for i in range(2, n+1) if primes[i]]

Sàng Sundaram

Sàng Sundaram là một thuật toán tìm số nguyên tố cực kỳ hiệu quả, được đặt theo tên của nhà toán học Ấn Độ Ashok Kumar Sundaram, người đã phát minh ra nó vào năm 1934.

Ý tưởng chính của thuật toán Sàng Sundaram là loại bỏ tất cả các số hình chữ nhật có dạng i+j+2ij với 1 ≤ i ≤ j trong khoảng từ 1 đến một giới hạn nào đó, ví dụ như 100 hoặc 1000. Các số còn lại trong khoảng đó sẽ là số nguyên tố.

Cụ thể, ta bắt đầu với danh sách gồm các số từ 1 đến (n-1)/2. Sau đó, ta tìm tất cả các số hình chữ nhật có dạng i+j+2ij với 1 ≤ i ≤ j trong danh sách đó và loại bỏ chúng khỏi danh sách. Các số còn lại trong danh sách là các số nguyên tố.

def sieve_of_sundaram(n):
    # Tạo một danh sách chứa tất cả các số từ 1 đến (n-1)/2
    numbers = list(range(1, (n-1)//2+1))

    # Tìm và loại bỏ các số hình chữ nhật có dạng i+j+2ij
    for i in range(1, (n-1)//2+1):
        for j in range(i, (n-i)//(2*i+1)+1):
            numbers[i+j+2*i*j-1] = 0

    # Trả về danh sách các số nguyên tố
    return [2] + [2*i+1 for i in numbers if i != 0]

Kiểm tra số nguyên tố bằng phương pháp Fermat

Phương pháp Fermat để kiểm tra số nguyên tố dựa trên định lý Fermat, một định lý nổi tiếng trong lý thuyết số. Định lý này cho biết nếu p là số nguyên tố và a là một số tự nhiên không chia hết cho p, thì a^(p-1) – 1 sẽ chia hết cho p.

Vì vậy, phương pháp Fermat sử dụng việc kiểm tra xem a^(p-1) – 1 có chia hết cho p hay không để quyết định xem p có phải là số nguyên tố hay không. Tuy nhiên, phương pháp này không hoàn toàn đáng tin cậy, vì tồn tại các số hợp số mà vẫn thỏa mãn định lý Fermat đối với một số cố định các số a.

Để sử dụng phương pháp Fermat để kiểm tra một số n có phải là số nguyên tố hay không, ta chọn một số nguyên tố a bất kỳ trong khoảng từ 2 đến n-1 và tính giá trị a^(n-1) mod n. Nếu giá trị này bằng 1, thì n có thể là số nguyên tố, còn nếu giá trị này khác 1, thì n không phải là số nguyên tố.

import random

def is_prime(n, k=5):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    for i in range(k):
        a = random.randint(2, n-1)
        if pow(a, n-1, n) != 1:
            return False

    return True

Lập trình Python