🔢 Phân tích Thừa số Nguyên tố

Khám phá thế giới các số nguyên tố và thuật toán phân tích

🎯 Số nguyên tố là gì?

Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có đúng hai ước số: 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11, 13, ...

🔍 Phân tích thừa số nguyên tố

Phân tích thừa số nguyên tố là quá trình biểu diễn một số tự nhiên dưới dạng tích của các số nguyên tố. Theo định lý cơ bản của số học, mọi số tự nhiên lớn hơn 1 đều có một cách phân tích duy nhất thành tích các thừa số nguyên tố.

⚙️ Thuật toán Trial Division

Đây là thuật toán cơ bản nhất để phân tích thừa số nguyên tố:

• Bắt đầu với số nhỏ nhất i = 2
• Kiểm tra xem n có chia hết cho i không
• Nếu có, chia n cho i và ghi nhận i là một thừa số
• Lặp lại cho đến khi n = 1
• Tối ưu: chỉ cần kiểm tra đến √n

⏱️ Độ phức tạp

Độ phức tạp thời gian của thuật toán Trial Division là O(√n), với n là số cần phân tích. Đây là thuật toán phù hợp cho các số không quá lớn.

🌟 Ứng dụng thực tế

Phân tích thừa số nguyên tố có nhiều ứng dụng quan trọng trong mật mã học (RSA), toán học rời rạc, và khoa học máy tính.

📱 Hướng dẫn sử dụng

Bước 1: Nhập số

Nhập số cần phân tích vào ô input (từ 2 đến 1,000,000). Ví dụ: 60, 120, 1001...

Bước 2: Phân tích

Nhấn nút "Phân tích" để xem kết quả. Hệ thống sẽ hiển thị:

• Các thừa số nguyên tố
• Biểu thức phân tích
• Từng bước thực hiện chi tiết
• Trực quan hóa kết quả

Bước 3: Xem chi tiết

Phần "Các bước thực hiện" sẽ mô tả từng bước của thuật toán, giúp bạn hiểu rõ quá trình phân tích.

🔧 Các tính năng khác

• Lý thuyết: Tìm hiểu kiến thức cơ bản về số nguyên tố
• Code Python: Xem mã nguồn chi tiết
• Nhật ký: Theo dõi lịch sử các phép tính
• Mobile-friendly: Tương thích trên mọi thiết bị

💡 Mẹo sử dụng

Thử với các số đặc biệt như số chính phương (16, 25, 36), số có nhiều thừa số (60, 120, 360), hoặc số nguyên tố (17, 23, 29) để thấy sự khác biệt.

🐍 Mã nguồn Python

def prime_factorization(n):
    """
    Phân tích số n thành tích các thừa số nguyên tố
    Sử dụng thuật toán Trial Division
    """
    factors = []
    steps = []
    original_n = n
    
    # Kiểm tra chia hết cho 2
    while n % 2 == 0:
        factors.append(2)
        steps.append(f"{n} ÷ 2 = {n//2}")
        n = n // 2
    
    # Kiểm tra các số lẻ từ 3 trở đi
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            steps.append(f"{n} ÷ {i} = {n//i}")
            n = n // i
        i += 2
    
    # Nếu n > 2, thì n là số nguyên tố
    if n > 2:
        factors.append(n)
        steps.append(f"{n} là số nguyên tố")
    
    return factors, steps

def format_factorization(factors):
    """Định dạng kết quả phân tích"""
    from collections import Counter
    
    factor_count = Counter(factors)
    result = []
    
    for factor in sorted(factor_count.keys()):
        count = factor_count[factor]
        if count == 1:
            result.append(str(factor))
        else:
            result.append(f"{factor}^{count}")
    
    return " × ".join(result)

def is_prime(n):
    """Kiểm tra số nguyên tố"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

# Ví dụ sử dụng
if __name__ == "__main__":
    number = int(input("Nhập số cần phân tích: "))
    
    if number < 2:
        print("Vui lòng nhập số >= 2")
    elif is_prime(number):
        print(f"{number} là số nguyên tố")
    else:
        factors, steps = prime_factorization(number)
        formatted = format_factorization(factors)
        
        print(f"\nSố {number} = {formatted}")
        print(f"Các thừa số: {factors}")
        print("\nCác bước thực hiện:")
        for step in steps:
            print(f"  {step}")

🔧 Cách chạy code:

1. Copy code trên vào file .py

2. Chạy: python prime_factorization.py

3. Nhập số cần phân tích khi được yêu cầu

📋 Nhật ký phân tích

Chưa có phép tính nào được thực hiện