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

NỘI DUNG

Các thuật toán

Dưới đây là một số thuật toán phổ biến liên quan đến số nguyên tố:

Kiểm tra số nguyên tố:
- Kiểm tra tất cả các ước của số đó: Đây là phương pháp đơn giản nhưng không hiệu quả. Đối với mỗi số nguyên dương n, kiểm tra xem n có chia hết cho bất kỳ số tự nhiên nào từ 2 đến √n không. Nếu có, thì n không phải là số nguyên tố.
- Kiểm tra số lượng ước của số đó: Số nguyên tố chỉ có hai ước là 1 và chính nó. Vì vậy, ta có thể kiểm tra số lượng ước của số đó để xác định xem nó có phải số nguyên tố hay không.
Sàng Eratosthenes:
- Đây là một thuật toán cổ điển để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương n cho trước.
- Bước đầu tiên là tạo một mảng các số từ 2 đến n và gán giá trị True cho tất cả các phần tử.
- Tiếp theo, duyệt qua từng phần tử trong mảng. Nếu giá trị của phần tử là True, đánh dấu tất cả các bội số của phần tử đó (không bao gồm phần tử đó) là False.
- Kết quả cuối cùng sẽ là tất cả các phần tử có giá trị là True trong mảng, chúng là các số nguyên tố.
Sàng Atkin:
- Sàng Atkin là một thuật toán hiệu quả hơn so với sàng Eratosthenes để tìm các số nguyên tố.
- Nó sử dụng ba mảng con để đánh dấu các số với các quy tắc khác nhau dựa trên các số modulo.
- Thuật toán duyệt qua các bội số của các số nguyên dương ở dạng a^2, b^2 và c^2, và đảo ngược giá trị của các phần tử tương ứng trong mảng con.
- Sau đó, thuật toán duyệt qua các số nằm trong phạm vi cho trước và thực hiện các phép toán modulo để kiểm tra các quy tắc và đánh dấu các số nguyên tố.
- Kết quả cuối cùng là tất cả các số nguyên tố trong phạm vi cho trước.

Cả hai thuật toán sàng Eratosthenes và sàng Atkin đều cho kết quả nhanh chóng và hiệu quả

Cài đặt các thuật toán

Kiểm tra số nguyên tố

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

# Ví dụ sử dụng
n = 17
if is_prime(n):
    print(f"{n} là số nguyên tố")
else:
    print(f"{n} không là số nguyên tố")

Trong ví dụ trên, chúng ta kiểm tra xem số n có chia hết cho bất kỳ số nguyên nào từ 2 đến căn bậc hai của n không. Nếu có, thì n không phải là số nguyên tố và trả về False. Nếu không có số nào chia hết, chúng ta kết luận n là số nguyên tố và trả về True.

Sàng Eratosthenes

def sieve_of_eratosthenes(n):
    primes = [True] * (n+1)
    primes[0] = primes[1] = False
    
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n+1, p):
                primes[i] = False
        p += 1
    
    result = []
    for i in range(2, n+1):
        if primes[i]:
            result.append(i)
    
    return result

# Ví dụ sử dụng
n = 100
prime_numbers = sieve_of_eratosthenes(n)
print(prime_numbers)

Sàng Atkin

import math

def sieve_of_atkin(limit):
    primes = [False] * (limit + 1)
    sqrt_limit = int(math.sqrt(limit)) + 1
    
    for x in range(1, sqrt_limit):
        for y in range(1, sqrt_limit):
            n = 4 * x**2 + y**2
            if n <= limit and (n % 12 == 1 or n % 12 == 5):
                primes[n] = not primes[n]
                
            n = 3 * x**2 + y**2
            if n <= limit and n % 12 == 7:
                primes[n] = not primes[n]
                
            n = 3 * x**2 - y**2
            if x > y and n <= limit and n % 12 == 11:
                primes[n] = not primes[n]
    
    for x in range(5, sqrt_limit):
        if primes[x]:
            for y in range(x**2, limit+1, x**2):
                primes[y] = False
    
    result = []
    for i in range(5, limit+1):
        if primes[i]:
            result.append(i)
    
    result.extend([2, 3])
    return result

# Ví dụ sử dụng
n = 100
prime_numbers = sieve_of_atkin(n)
print(prime_numbers)

Lập trình Python