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

Hướng dẫn này so sánh ba phương pháp tìm số nguyên tố và đo thời gian thực thi của từng phương pháp bằng module time.

Phương pháp 1: Kiểm tra đơn giản

Kiểm tra tính chia hết từ 2 đến n-1.

Mã nguồn

import time

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

start_time = time.time()
primes = 0
for i in range(100000):
    if is_prime(i):
        primes += 1
print(f'Total primes in the range {primes}')
end_time = time.time()
print(f'Execution time: {end_time - start_time}')

Kết quả

Total primes in the range 9594
Execution time: 63.1301212310791

Phương pháp 2: Tối ưu hóa bằng căn bậc hai

Chỉ kiểm tra đến √n thay vì n-1.

Mã nguồn

import time
import math

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

start_time = time.time()
primes = 0
for i in range(100000):
    if is_prime(i):
        primes += 1
print(f'Total primes in the range {primes}')
end_time = time.time()
print(f'Execution time: {end_time - start_time}')

Kết quả

Total primes in the range 9592
Execution time: 0.2039644718170166

Phương pháp 3: Bỏ qua các số chẵn

Ngoại trừ số 2, không có số chẵn nào là số nguyên tố. Chỉ kiểm tra các số lẻ.

Mã nguồn

import time
import math

def is_prime(n):
    if n <= 1:
        return False
    elif n == 2:
        return True
    elif n > 2 and n % 2 == 0:
        return False
    else:
        for i in range(3, int(math.sqrt(n)) + 1, 2):
            if n % i == 0:
                return False
        return True

start_time = time.time()
primes = 0
for i in range(100000):
    if is_prime(i):
        primes += 1
print(f'Total primes in the range {primes}')
end_time = time.time()
print(f'Execution time: {end_time - start_time}')

Kết quả

Total primes in the range 9592
Execution time: 0.10342741012573242

Kết luận

Phương pháp 3 nhanh nhất nhờ giảm số lần lặp. Thời gian giảm từ 63 giây xuống 0.1 giây. Hãy thử nghiệm thêm với Sieve of Eratosthenes để hiệu quả hơn nữa.