Các phương pháp tìm số nguyên tố trong Python

Số nguyên tố: số nguyên dương > 1, chỉ chia hết cho 1 và chính nó. 1 không phải số nguyên tố.

Phương pháp 1: Vòng lặp lồng đơn giản

def prime_method1(n):
    primes = []
    for num in range(2, n):
        is_prime = True
        for i in range(2, num):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

print(prime_method1(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Phương pháp 2: Break sớm (tối ưu nhẹ)

def prime_method2(n):
    primes = []
    for num in range(2, n+1):
        is_prime = True
        for i in range(2, num):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

Phương pháp 3: Chỉ kiểm tra đến √n (tối ưu mạnh)

def prime_method3(n):
    primes = []
    for num in range(2, n):
        is_prime = True
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

print(prime_method3(50))

Phương pháp 4: Sieve of Eratosthenes (hiệu quả nhất cho n lớn)

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, val in enumerate(is_prime) if val]

print(sieve(1000000))  # Rất nhanh cho n lớn

So sánh độ phức tạp

Kiểm tra 1 số (is_prime)

def is_prime(n):
    if n < 2: return False
    if n % 2 == 0: return n == 2
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0: return False
    return True