Liệt kê các ước nguyên tố của số nguyên N

NỘI DUNG

Yêu cầu của bài toán

Nhập số nguyên dương N. Liệt kê các ước nguyên tố của N.

Thuật toán và cài đặt bài toán

Để liệt kê các ước nguyên tố của một số nguyên dương N, ta cần thực hiện các bước sau:

Khai báo số nguyên dương N và tạo một danh sách để lưu các ước nguyên tố của N.
Sử dụng một vòng lặp từ 2 đến căn bậc hai của N để tìm các ước nguyên tố của N.
Trong vòng lặp, nếu N chia hết cho i thì thêm i vào danh sách các ước nguyên tố của N, sau đó kiểm tra nếu N/i là một số nguyên tố thì thêm N/i vào danh sách này.
Nếu danh sách ước nguyên tố của N là rỗng, thì N là một số nguyên tố và chính nó là ước nguyên tố của nó.
Hiển thị danh sách các ước nguyên tố của N.

Dưới đây là đoạn mã Python để thực hiện các bước trên:

import math

N = int(input("Nhap mot so nguyen duong: "))
prime_factors = []

for i in range(2, int(math.sqrt(N))+1):
    if N % i == 0:
        prime_factors.append(i)
        if i != N // i and is_prime(N // i):
            prime_factors.append(N // i)

if not prime_factors:
    prime_factors.append(N)

print("Cac uoc nguyen to cua", N, "la:", prime_factors)

Trong đó, hàm is_prime dùng để kiểm tra một số có phải là số nguyên tố hay không. Các bạn có thể sử dụng đoạn mã sau để định nghĩa hàm này:

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

Lưu ý rằng khi kiểm tra N/i là số nguyên tố, ta cần sử dụng hàm is_prime được định nghĩa ở trên để kiểm tra.

Các thuật toán xử lý bài toán

Bài toán liệt kê các ước nguyên tố của một số nguyên dương N có thể được giải bằng nhiều thuật toán khác nhau. Sau đây là một số thuật toán phổ biến để giải bài toán này:

Sử dụng vòng lặp: Sử dụng vòng lặp để duyệt qua từng số từ 2 đến N-1 và kiểm tra xem nó có phải là ước nguyên tố của N hay không. Nếu có, thêm số đó vào danh sách các ước nguyên tố.
Sử dụng sàng nguyên tố: Sử dụng sàng nguyên tố để tìm tất cả các số nguyên tố trong khoảng từ 2 đến căn bậc hai của N, sau đó kiểm tra xem các số nguyên tố đó có phải là ước nguyên tố của N hay không. Nếu có, thêm số đó vào danh sách các ước nguyên tố.
Sử dụng phân tích ra thừa số nguyên tố: Phân tích N thành tích các số nguyên tố, sau đó liệt kê các ước nguyên tố của N là các số được tạo thành bởi các ước nguyên tố này.
Sử dụng phương pháp brute force: Sử dụng phương pháp brute force để duyệt qua từng số từ 2 đến N-1 và kiểm tra xem nó có phải là ước của N hay không. Nếu có, kiểm tra xem nó có phải là ước nguyên tố hay không và thêm số đó vào danh sách các ước nguyên tố.
Sử dụng phương pháp đệ quy: Sử dụng phương pháp đệ quy để tìm các ước nguyên tố của N.

Mỗi thuật toán có những ưu điểm và nhược điểm riêng, và thời gian thực hiện của chúng cũng khác nhau. Tuy nhiên, trong trường hợp số N không quá lớn, các thuật toán trên đều có thể giải bài toán một cách hiệu quả.

Đánh giá độ phức tạp của các thuật toán

Độ phức tạp của các thuật toán sẽ được đánh giá dựa trên thời gian thực hiện của chúng. Dưới đây là đánh giá độ phức tạp của 5 thuật toán liệt kê các ước nguyên tố của một số nguyên dương N:

Sử dụng vòng lặp: Thuật toán này sử dụng một vòng lặp để duyệt qua từng số từ 2 đến N-1, và với mỗi số này, kiểm tra xem nó có phải là ước nguyên tố của N hay không. Thời gian thực hiện của thuật toán này là O(N).
Sử dụng sàng nguyên tố: Thuật toán này sử dụng sàng nguyên tố để tìm tất cả các số nguyên tố trong khoảng từ 2 đến căn bậc hai của N, sau đó kiểm tra xem các số nguyên tố này có phải là ước nguyên tố của N hay không. Thời gian thực hiện của thuật toán này là O(sqrt(N) * log log(sqrt(N))).
Sử dụng phân tích ra thừa số nguyên tố: Thuật toán này sử dụng phân tích N thành tích các số nguyên tố, sau đó liệt kê các ước nguyên tố của N là các số được tạo thành bởi các ước nguyên tố này. Thời gian thực hiện của thuật toán này phụ thuộc vào độ phức tạp của thuật toán phân tích thừa số nguyên tố, có thể là O(sqrt(N) * log log(sqrt(N))).
Sử dụng phương pháp brute force: Thuật toán này duyệt qua từng số từ 2 đến N-1 và kiểm tra xem nó có phải là ước của N hay không. Nếu có, kiểm tra xem nó có phải là ước nguyên tố hay không và thêm số đó vào danh sách các ước nguyên tố. Thời gian thực hiện của thuật toán này là O(N).
Sử dụng phương pháp đệ quy: Thuật toán này sử dụng phương pháp đệ quy để tìm các ước nguyên tố của N. Độ phức tạp của thuật toán này phụ thuộc vào chiều sâu của đệ quy và số lượng ước nguyên tố của N. Trong trường hợp tốt nhất, thời gian thực hiện là O(1), còn trong trường hợp xấu nhất thì độ phức tạp là O(N).

Trong số các thuật toán đã đề cập ở trên, thuật toán sử dụng sàng nguyên tố là tối ưu nhất về mặt độ phức tạp, với độ phức tạp là O(sqrt(N) * log log(sqrt(N))). Vì thời gian thực hiện của nó không phụ thuộc trực tiếp vào giá trị của N, mà chỉ phụ thuộc vào căn bậc hai của N. Điều này làm cho thuật toán này rất hiệu quả đối với các số N lớn.

Trong khi đó, các thuật toán còn lại đều có độ phức tạp lớn hơn, với thuật toán sử dụng vòng lặp và phương pháp brute force có độ phức tạp là O(N), và thuật toán sử dụng phương pháp đệ quy có độ phức tạp cao nhất là O(N) trong trường hợp xấu nhất. Do đó, khi cần tìm tất cả các ước nguyên tố của một số nguyên dương N, nên sử dụng thuật toán sàng nguyên tố để đạt được hiệu quả cao nhất.

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

Thuật toán sàng nguyên tố

Các bước giải bài toán liệt kê tất cả các ước nguyên tố của một số nguyên dương N bằng sàng nguyên tố như sau:

Bước 1: Nhập số nguyên dương N cần tìm tất cả các ước nguyên tố của nó.

Bước 2: Khởi tạo một mảng bool có kích thước N+1, đặt tất cả các giá trị là true.

Bước 3: Đánh dấu số 0 và số 1 trong mảng bool là false.

Bước 4: Lặp từ 2 đến căn bậc hai của N, nếu giá trị của mảng bool tại i là true, thực hiện bước 5.

Bước 5: Với mỗi số nguyên tố i từ 2 đến N/i, đánh dấu i * j là false trong mảng bool, với j từ 2 đến N/i.

Bước 6: Liệt kê tất cả các ước nguyên tố của N dựa trên các phần tử có giá trị true trong mảng bool từ 2 đến N.

Ví dụ: Giả sử cần tìm tất cả các ước nguyên tố của số 30. Theo các bước trên, ta có thể thực hiện như sau:

Bước 1: N = 30.

Bước 2: Khởi tạo mảng bool với kích thước là 31, tất cả các phần tử đều có giá trị là true.

Bước 3: Đánh dấu phần tử thứ 0 và phần tử thứ 1 của mảng bool là false.

Bước 4: Vì căn bậc hai của 30 là 5, nên lặp từ i = 2 đến 5.

Bước 5: Tại i = 2, đánh dấu false các phần tử 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.

Tại i = 3, đánh dấu false các phần tử 6, 9, 12, 15, 18, 21, 24, 27, 30.

Tại i = 4, không thực hiện gì vì 4 đã được đánh dấu false trong lần lặp tại i = 2.

Bước 6: Liệt kê tất cả các ước nguyên tố của 30 từ các phần tử có giá trị true trong mảng bool từ 2 đến 30, ta có: 2, 3, 5.

Vì vậy, các ước nguyên tố của 30 là 2, 3, 5.

Dưới đây là cách cài đặt thuật toán sàng nguyên tố với Python:

def sieve_prime_factors(n):
    # Tạo một danh sách chứa các ước nguyên tố của n
    prime_factors = []
    
    # Tìm tất cả các số nguyên tố từ 2 đến căn bậc hai của n
    primes = SieveOfEratosthenes(int(n**0.5)+1)
    
    # Lặp qua danh sách các số nguyên tố và tìm các ước nguyên tố của n
    for prime in primes:
        # Nếu prime là ước nguyên tố của n, thêm prime vào danh sách prime_factors
        while n % prime == 0:
            prime_factors.append(prime)
            n = n // prime
            
    # Nếu n còn lại lớn hơn 1 sau khi đã tìm hết các ước nguyên tố trong primes
    # thì nó chắc chắn cũng là một số nguyên tố
    if n > 1:
        prime_factors.append(n)
        
    return prime_factors

def SieveOfEratosthenes(n):
    # Khởi tạo một mảng bool có kích thước n+1, đặt tất cả các giá trị là true
    primes = [True for i in range(n+1)]
    # Đánh dấu số 0 và số 1 trong mảng bool là false
    primes[0] = False
    primes[1] = False
    
    # Lặp từ 2 đến căn bậc hai của n
    p = 2
    while (p * p <= n):
        # Nếu primes[p] là True, đánh dấu false tất cả các phần tử là bội số của p
        if (primes[p] == True):
            for i in range(p * 2, n+1, p):
                primes[i] = False
        p += 1
    
    # Liệt kê tất cả các số nguyên tố từ 2 đến n
    prime_list = []
    for p in range(2, n+1):
        if primes[p]:
            prime_list.append(p)
    
    return prime_list

# Ví dụ: liệt kê các ước nguyên tố của số nguyên dương N = 1234567890
N = 1234567890
prime_factors = sieve_prime_factors(N)
print("Các ước nguyên tố của", N, "là:", prime_factors)

Thuật toán sử dụng vòng lặp

Để cài đặt thuật toán sàng nguyên tố sử dụng vòng lặp, ta có thể làm như sau:

def prime_factors(n):
    # Tạo một danh sách chứa các ước nguyên tố của n
    prime_factors = []
    
    # Lặp qua các số nguyên từ 2 đến n
    for i in range(2, n+1):
        # Kiểm tra xem i có phải là số nguyên tố hay không
        is_prime = True
        for j in range(2, int(i**0.5)+1):
            if i % j == 0:
                is_prime = False
                break
        # Nếu i là số nguyên tố và là ước của n, thêm i vào danh sách prime_factors
        if is_prime and n % i == 0:
            prime_factors.append(i)
    
    return prime_factors

# Ví dụ: liệt kê các ước nguyên tố của số nguyên dương N = 1234567890
N = 1234567890
prime_factors = prime_factors(N)
print("Các ước nguyên tố của", N, "là:", prime_factors)

Thuật toán phân tích ra thừa số nguyên tố

Để cài đặt thuật toán sàng nguyên tố sử dụng phân tích ra thừa số nguyên tố, ta có thể làm như sau:

def prime_factors(n):
    # Tạo một danh sách chứa các ước nguyên tố của n
    prime_factors = []
    
    # Duyệt qua các ước nguyên tố của n
    i = 2
    while i * i <= n:
        # Kiểm tra i có phải là ước của n hay không
        if n % i == 0:
            # Nếu i là ước của n, thêm i vào danh sách prime_factors
            prime_factors.append(i)
            
            # Chia n cho i cho đến khi n không còn chia được i
            while n % i == 0:
                n //= i
                
        # Tăng i lên 1
        i += 1
    
    # Nếu n vẫn còn lớn hơn 1, nghĩa là n là một số nguyên tố lơn hơn 2
    if n > 1:
        prime_factors.append(n)
    
    return prime_factors

# Ví dụ: liệt kê các ước nguyên tố của số nguyên dương N = 1234567890
N = 1234567890
prime_factors = prime_factors(N)
print("Các ước nguyên tố của", N, "là:", prime_factors)

Trong đoạn mã này, ta duyệt qua các ước nguyên tố của n bằng cách duyệt qua các số nguyên từ 2 đến căn bậc hai của n. Nếu số đó là ước của n, ta thêm số đó vào danh sách prime_factors và chia n cho số đó cho đến khi n không còn chia được số đó. Nếu n vẫn còn lớn hơn 1, nghĩa là n là một số nguyên tố lơn hơn 2 và ta thêm n vào danh sách prime_factors. Mã này có độ phức tạp là O(sqrt(N)), tức là nhanh hơn rất nhiều so với cách sử dụng vòng lặp.

Thuật toán brute force

Thuật toán sàng nguyên tố sử dụng phương pháp brute force sẽ kiểm tra từng số nguyên dương từ 2 đến N-1 để xác định xem số đó có phải là số nguyên tố hay không. Để cài đặt thuật toán này, ta có thể làm như sau:

def is_prime(n):
    # Trường hợp đặc biệt: n là số nguyên tố nhỏ hơn 2
    if n < 2:
        return False
    
    # Kiểm tra từng số nguyên dương từ 2 đến n-1
    for i in range(2, n):
        # Nếu n chia hết cho một số trong đoạn 2 đến n-1, n không phải là số nguyên tố
        if n % i == 0:
            return False
    
    # Nếu không có số nào trong đoạn 2 đến n-1 chia hết cho n, n là số nguyên tố
    return True

# Ví dụ: liệt kê các số nguyên tố trong đoạn từ 1 đến 100
for i in range(1, 101):
    if is_prime(i):
        print(i, end=' ')

Trong đoạn mã này, ta sử dụng vòng lặp để duyệt qua các số nguyên dương từ 2 đến n-1. Với mỗi số đó, ta kiểm tra xem nó có phải là ước của n hay không. Nếu nó là ước của n, ta trả về False vì n không phải là số nguyên tố. Nếu không có số nào trong đoạn 2 đến n-1 chia hết cho n, ta trả về True vì n là số nguyên tố. Mã này có độ phức tạp là O(N^2), nghĩa là rất chậm khi N lớn.

Thuật toán đệ quy

Thuật toán sàng nguyên tố sử dụng phương pháp đệ quy sẽ kiểm tra xem n có chia hết cho một số nguyên dương trong đoạn từ 2 đến căn bậc hai của n hay không. Nếu không, n là số nguyên tố. Nếu có, n không phải là số nguyên tố. Để cài đặt thuật toán này, ta có thể làm như sau:

import math

def is_prime(n, i=2):
    # Trường hợp đặc biệt: n là số nguyên tố nhỏ hơn 2
    if n < 2:
        return False
    
    # Trường hợp cơ bản: n là số nguyên tố
    if i > math.sqrt(n):
        return True
    
    # Kiểm tra xem n có chia hết cho i hay không
    if n % i == 0:
        return False
    
    # Nếu không, kiểm tra tiếp i+1
    return is_prime(n, i+1)

# Ví dụ: liệt kê các số nguyên tố trong đoạn từ 1 đến 100
for i in range(1, 101):
    if is_prime(i):
        print(i, end=' ')

Trong đoạn mã này, ta sử dụng đệ quy để kiểm tra xem n có phải là số nguyên tố hay không. Ta đưa vào hàm is_prime() hai tham số là n và i (mặc định i=2). Ban đầu, ta kiểm tra trường hợp đặc biệt nếu n < 2 thì trả về False. Nếu không, ta kiểm tra trường hợp cơ bản, nếu i > căn bậc hai của n thì trả về True vì n không chia hết cho bất kỳ số nguyên dương nào từ 2 đến căn bậc hai của n. Nếu không, ta kiểm tra xem n có chia hết cho i không. Nếu có, trả về False. Nếu không, ta gọi đệ quy lại hàm is_prime() với tham số n và i+1 để kiểm tra tiếp. Mã này có độ phức tạp là O(√N), nghĩa là nhanh hơn rất nhiều so với phương pháp brute force.

Tổng kết

Bài toán tìm các ước nguyên tố của một số nguyên dương N là một bài toán cơ bản trong lĩnh vực số học và thuật toán. Ta có thể giải bài toán này bằng nhiều phương pháp khác nhau, chúng ta nên sử dụng 1 trong 4 phương pháp tối ưu hơn thuật toán sử dụng vòng lặp:

Sàng nguyên tố: phương pháp này dựa trên việc loại bỏ các số hợp thành của các số nguyên tố đã biết để tìm ra các số nguyên tố còn lại. Thuật toán này có độ phức tạp thời gian là O(N*log(log(N))), tuy nhiên nó có thể tốn nhiều bộ nhớ hơn các phương pháp khác.
Phân tích ra thừa số nguyên tố: phương pháp này dựa trên việc phân tích số N thành tích các số nguyên tố để tìm ra các ước nguyên tố của N. Thuật toán này có độ phức tạp thời gian là O(sqrt(N)).
Brute force: phương pháp này dựa trên việc kiểm tra lần lượt từng số từ 1 đến N để tìm ra các ước nguyên tố của N. Thuật toán này có độ phức tạp thời gian là O(N).
Đệ quy: phương pháp này cũng sử dụng phân tích ra thừa số nguyên tố để kiểm tra xem một số có phải số nguyên tố hay không. Thuật toán này có độ phức tạp thời gian là O(sqrt(N)).

Trong các phương pháp trên, sàng nguyên tố là phương pháp tối ưu nhất về mặt độ phức tạp thời gian. Tuy nhiên, đối với các số N lớn, phương pháp này có thể tốn nhiều bộ nhớ hơn. Nếu không cần liệt kê các ước nguyên tố một cách chi tiết, các phương pháp phân tích ra thừa số nguyên tố hoặc đệ quy có thể được sử dụng để giải bài toán này./.

Lập trình Python