Phân tích các phương pháp tìm số nguyên tố trong Python

Số nguyên tố là số nguyên dương > 1 chỉ chia hết cho 1 và chính nó. Bài viết so sánh 3 thuật toán kiểm tra số nguyên tố theo hiệu năng.

Phương pháp 1: Kiểm tra tất cả ước số (2 đến n-1)

Độ phức tạp: O(n)

import time

def is_prime_v1(n):
    if n <= 1:
        return False
    for divisor in range(2, n):
        if n % divisor == 0:
            return False
    return True

# Test hiệu năng
start = time.time()
count = sum(1 for i in range(1, 10001) if is_prime_v1(i))
end = time.time()
print(f"Số nguyên tố ≤ 10000: {count}")
print(f"Thời gian: {end - start:.4f}s")

Kết quả

Số nguyên tố ≤ 10000: 1229
Thời gian: ~2.31s

Phương pháp 2: Kiểm tra đến căn bậc 2 (√n)

Nếu n có ước > √n, thì ước cặp của nó < √n. Chỉ cần kiểm tra đến √n.

Độ phức tạp: O(√n)

import math, time

def is_prime_v2(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

start = time.time()
count = sum(1 for i in range(1, 10001) if is_prime_v2(i))
end = time.time()
print(f"Số nguyên tố ≤ 10000: {count}")
print(f"Thời gian: {end - start:.4f}s")

Kết quả

Số nguyên tố ≤ 10000: 1229
Thời gian: ~0.053s

Nhanh hơn ~43 lần so với phương pháp 1.

Phương pháp 3: Sàng Eratosthenes (Sieve of Eratosthenes)

Tìm tất cả số nguyên tố ≤ n bằng cách loại bội số.

Độ phức tạp: O(n log log n) - nhanh nhất cho tìm tất cả số nguyên tố trong khoảng.

import time

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    
    return [i for i, prime in enumerate(is_prime) if prime]

start = time.time()
primes = sieve(10000)
end = time.time()
print(f"Số nguyên tố ≤ 10000: {len(primes)}")
print(f"Thời gian: {end - start:.6f}s")

Kết quả

Số nguyên tố ≤ 10000: 1229
Thời gian: ~0.001s

Bảng so sánh

Kết luận

• Kiểm tra 1 số: dùng phương pháp √n
• Tìm tất cả SNT ≤ n: dùng Sàng Eratosthenes
• Tránh phương pháp O(n) trừ khi n rất nhỏ