Số hoàn hảo

Thuật Toán Kiểm Tra Số Hoàn Hảo

🎯 Số Hoàn Hảo Là Gì?

Số hoàn hảo là một số nguyên dương bằng tổng của tất cả các ước số dương thực sự của nó (không bao gồm chính nó).

📐 Định Nghĩa Toán Học

Một số n được gọi là số hoàn hảo nếu: σ(n) - n = n

Trong đó σ(n) là tổng của tất cả các ước số dương của n.

🌟 Ví Dụ Cổ Điển

Số 6: Các ước số thực sự: 1, 2, 3

Tổng: 1 + 2 + 3 = 6 ✅

Số 28: Các ước số thực sự: 1, 2, 4, 7, 14

Tổng: 1 + 2 + 4 + 7 + 14 = 28 ✅

🔍 Thuật Toán Kiểm Tra

Tìm tất cả các ước số thực sự của n (từ 1 đến n/2)
Tính tổng các ước số tìm được
So sánh tổng với n
Nếu bằng nhau → Số hoàn hảo

📊 Độ Phức Tạp

Thời gian: O(√n) - Chỉ cần kiểm tra đến √n

Không gian: O(1) - Chỉ cần biến đếm

🔢 Nhập số cần kiểm tra:

🐍 Code Python - Thuật Toán Số Hoàn Hảo

📝 Phiên Bản Cơ Bản

def is_perfect_number(n):
    """
    Kiểm tra số n có phải là số hoàn hảo không
    Args: n (int) - Số cần kiểm tra
    Returns: bool - True nếu là số hoàn hảo
    """
    if n <= 1:
        return False
    
    sum_divisors = 0
    
    # Tìm các ước số từ 1 đến n//2
    for i in range(1, n // 2 + 1):
        if n % i == 0:
            sum_divisors += i
    
    return sum_divisors == n

# Test
print(is_perfect_number(6))   # True
print(is_perfect_number(28))  # True
print(is_perfect_number(12))  # False

⚡ Phiên Bản Tối Ưu - O(√n)

import math

def is_perfect_optimized(n):
    """
    Thuật toán tối ưu kiểm tra số hoàn hảo - O(√n)
    
    Ý tưởng: Thay vì kiểm tra tất cả số từ 1 đến n-1,
    ta chỉ cần kiểm tra từ 1 đến √n và tìm cặp ước số
    
    Args:
        n (int): Số cần kiểm tra
    Returns:
        bool: True nếu là số hoàn hảo, False nếu không
    """
    # Trường hợp đặc biệt
    if n <= 1:
        return False
    
    # Khởi tạo tổng ước số với 1 (luôn là ước số)
    sum_divisors = 1
    
    # Chỉ duyệt từ 2 đến √n
    sqrt_n = int(math.sqrt(n))
    
    for i in range(2, sqrt_n + 1):
        if n % i == 0:  # i là ước số của n
            # Thêm ước số i
            sum_divisors += i
            
            # Thêm ước số tương ứng n/i (nếu khác i)
            corresponding_divisor = n // i
            if i != corresponding_divisor:
                sum_divisors += corresponding_divisor
    
    # So sánh tổng với n
    return sum_divisors == n

def is_perfect_with_details(n):
    """
    Phiên bản chi tiết - trả về kết quả và danh sách ước số
    """
    if n <= 1:
        return False, [], 0
    
    divisors = [1]  # Danh sách ước số
    sum_divisors = 1
    sqrt_n = int(math.sqrt(n))
    
    for i in range(2, sqrt_n + 1):
        if n % i == 0:
            divisors.append(i)
            sum_divisors += i
            
            corresponding = n // i
            if i != corresponding:
                divisors.append(corresponding)
                sum_divisors += corresponding
    
    # Sắp xếp danh sách ước số
    divisors.sort()
    
    return sum_divisors == n, divisors, sum_divisors

# Test với ví dụ
print("=== TEST THUẬT TOÁN TỐI ƯU ===")
test_numbers = [6, 28, 12, 496, 1000]

for num in test_numbers:
    is_perfect, divisors, total = is_perfect_with_details(num)
    print(f"Số {num}:")
    print(f"  Ước số: {divisors}")
    print(f"  Tổng: {total}")
    print(f"  Kết quả: {'✅ Hoàn hảo' if is_perfect else '❌ Không hoàn hảo'}")
    print()

🚀 Thuật Toán Siêu Tối Ưu - Mersenne Primes

def is_mersenne_prime(p):
    """
    Kiểm tra p có phải là số nguyên tố Mersenne không
    Số nguyên tố Mersenne có dạng 2^p - 1 (với p là số nguyên tố)
    """
    if p < 2:
        return False
    
    # Kiểm tra p có phải số nguyên tố không
    if p == 2:
        return True
    if p % 2 == 0:
        return False
    
    for i in range(3, int(p**0.5) + 1, 2):
        if p % i == 0:
            return False
    
    return True

def generate_perfect_from_mersenne(limit):
    """
    Sinh số hoàn hảo từ công thức Euclid-Euler:
    Nếu 2^p - 1 là số nguyên tố, thì 2^(p-1) × (2^p - 1) là số hoàn hảo
    
    Đây là cách tìm TẤT CẢ số hoàn hảo chẵn!
    """
    perfect_numbers = []
    
    p = 2
    while p < 20:  # Giới hạn để tránh số quá lớn
        if is_mersenne_prime(p):
            mersenne = (2 ** p) - 1
            perfect = (2 ** (p - 1)) * mersenne
            
            if perfect <= limit:
                perfect_numbers.append(perfect)
            else:
                break
        
        p += 1
    
    return perfect_numbers

# Sinh số hoàn hảo bằng công thức Mersenne
print("=== SỐ HOÀN HẢO TỪ CÔNG THỨC MERSENNE ===")
mersenne_perfects = generate_perfect_from_mersenne(10000)
print(f"Số hoàn hảo ≤ 10,000: {mersenne_perfects}")

# So sánh hiệu suất
import time

def benchmark_comparison(n):
    """So sánh hiệu suất các thuật toán"""
    
    # Thuật toán cơ bản O(n)
    start = time.time()
    result1 = is_perfect_number(n)
    time1 = time.time() - start
    
    # Thuật toán tối ưu O(√n)
    start = time.time()
    result2 = is_perfect_optimized(n)
    time2 = time.time() - start
    
    print(f"Số {n}:")
    print(f"  Cơ bản O(n): {time1:.6f}s - {result1}")
    print(f"  Tối ưu O(√n): {time2:.6f}s - {result2}")
    print(f"  Tăng tốc: {time1/time2:.1f}x")
    print()

# Test hiệu suất
print("=== SO SÁNH HIỆU SUẤT ===")
for test_num in [496, 8128, 33550336]:
    benchmark_comparison(test_num)

📊 Phân Tích Chi Tiết & Visualization

import matplotlib.pyplot as plt
import numpy as np

def analyze_perfect_number(n):
    """
    Phân tích chi tiết một số hoàn hảo
    """
    print(f"=== PHÂN TÍCH SỐ {n} ===")
    
    is_perfect, divisors, total = is_perfect_with_details(n)
    
    print(f"Số kiểm tra: {n}")
    print(f"Số ước số: {len(divisors)}")
    print(f"Danh sách ước số: {divisors}")
    print(f"Tổng ước số: {total}")
    print(f"Công thức: {' + '.join(map(str, divisors))} = {total}")
    print(f"Kết luận: {'✅ SỐ HOÀN HẢO' if is_perfect else '❌ KHÔNG PHẢI SỐ HOÀN HẢO'}")
    
    # Phân tích cấu trúc
    if len(divisors) > 1:
        ratio = divisors[-2] / divisors[0] if len(divisors) > 1 else 0
        print(f"Tỷ lệ ước lớn nhất/nhỏ nhất: {ratio:.2f}")
        
    print("-" * 50)
    return is_perfect, divisors, total

def find_perfect_efficient(limit):
    """
    Tìm số hoàn hảo hiệu quả với thông tin chi tiết
    """
    print(f"🔍 TÌM KIẾM SỐ HOÀN HẢO TỪ 1 ĐẾN {limit}")
    print("=" * 60)
    
    perfect_numbers = []
    checked = 0
    
    for num in range(1, limit + 1):
        checked += 1
        if checked % 1000 == 0:
            print(f"Đã kiểm tra: {checked}/{limit} ({checked/limit*100:.1f}%)")
        
        if is_perfect_optimized(num):
            perfect_numbers.append(num)
            print(f"🎉 Tìm thấy số hoàn hảo: {num}")
            analyze_perfect_number(num)
    
    print(f"\n📋 KẾT QUẢ CUỐI CÙNG:")
    print(f"Phạm vi kiểm tra: 1 - {limit}")
    print(f"Số hoàn hảo tìm được: {len(perfect_numbers)}")
    print(f"Danh sách: {perfect_numbers}")
    
    return perfect_numbers

# Chạy phân tích
print("=== DEMO PHÂN TÍCH CHI TIẾT ===")
for num in [6, 28, 12, 496]:
    analyze_perfect_number(num)

# Tìm kiếm trong phạm vi nhỏ
result = find_perfect_efficient(1000)

# Thống kê
def perfect_number_statistics():
    """
    Thống kê về số hoàn hảo
    """
    known_perfects = [6, 28, 496, 8128, 33550336, 8589869056, 137438691328]
    
    print("\n📊 THỐNG KÊ SỐ HOÀN HẢO:")
    print("=" * 40)
    print(f"Số hoàn hảo đã biết: {len(known_perfects)}")
    print("Danh sách các số hoàn hảo đầu tiên:")
    
    for i, perfect in enumerate(known_perfects[:5], 1):
        digits = len(str(perfect))
        print(f"  {i}. {perfect:,} ({digits} chữ số)")
    
    print(f"\nGhi chú:")
    print(f"- Tất cả số hoàn hảo chẵn đều có dạng 2^(p-1) × (2^p - 1)")
    print(f"- Chưa tìm thấy số hoàn hảo lẻ nào")
    print(f"- Số hoàn hảo lớn nhất hiện biết có hơn 49 triệu chữ số!")

perfect_number_statistics()

📖 Hướng Dẫn Sử Dụng

🎯 Cách Sử Dụng Ứng Dụng

Tab Lý Thuyết: Tìm hiểu khái niệm số hoàn hảo
Tab Mô Phỏng: Kiểm tra số cụ thể hoặc tìm kiếm số hoàn hảo
Tab Code: Xem và học code Python
Tab Nhật Ký: Theo dõi lịch sử kiểm tra

🔍 Hướng Dẫn Mô Phỏng

Kiểm tra đơn: Nhập số và nhấn "Kiểm Tra"
Tìm kiếm: Nhấn "Tìm Số Hoàn Hảo" để tìm từ 1-1000
Theo dõi: Xem quá trình thực hiện từng bước
Kết quả: Màu xanh = hoàn hảo, đỏ = không hoàn hảo

💡 Mẹo Sử Dụng

Thử các số nhỏ trước: 6, 28, 496
Số hoàn hảo rất hiếm, chỉ có 4 số < 10,000
Sử dụng trên mobile: Giao diện tự động điều chỉnh
Nhúng vào blog: Copy toàn bộ HTML

🌐 Tương Thích

✅ Desktop: Chrome, Firefox, Safari, Edge
✅ Mobile: iOS Safari, Android Chrome
✅ Blogger/Blogspot: Paste HTML trực tiếp
✅ WordPress: Sử dụng HTML widget

🔧 Tùy Chỉnh

Thay đổi màu sắc trong CSS
Điều chỉnh giới hạn tìm kiếm
Thêm hiệu ứng animation
Mở rộng tính năng phân tích

📋 Nhật Ký Kiểm Tra

Ghi lại tất cả các lần kiểm tra số hoàn hảo

Khởi tạo ứng dụng - 30/06/2025

🎉 Chào mừng bạn đến với ứng dụng kiểm tra số hoàn hảo!

Số hoàn hảo

🔢 Thuật Toán Số Hoàn Hảo

🎯 Số Hoàn Hảo Là Gì?

📐 Định Nghĩa Toán Học

🌟 Ví Dụ Cổ Điển

🔍 Thuật Toán Kiểm Tra

📊 Độ Phức Tạp

🔄 Quá Trình Thực Hiện

🐍 Code Python - Thuật Toán Số Hoàn Hảo

📝 Phiên Bản Cơ Bản

⚡ Phiên Bản Tối Ưu - O(√n)

🚀 Thuật Toán Siêu Tối Ưu - Mersenne Primes

📊 Phân Tích Chi Tiết & Visualization

📖 Hướng Dẫn Sử Dụng

🎯 Cách Sử Dụng Ứng Dụng

🔍 Hướng Dẫn Mô Phỏng

💡 Mẹo Sử Dụng

🌐 Tương Thích

🔧 Tùy Chỉnh

📋 Nhật Ký Kiểm Tra

Post a Comment

Không có nhận xét nào

Bài đăng phổ biến

Liên hệ với chúng tôi

Số hoàn hảo

🔢 Thuật Toán Số Hoàn Hảo

🎯 Số Hoàn Hảo Là Gì?

📐 Định Nghĩa Toán Học

🌟 Ví Dụ Cổ Điển

🔍 Thuật Toán Kiểm Tra

📊 Độ Phức Tạp

🔄 Quá Trình Thực Hiện

🐍 Code Python - Thuật Toán Số Hoàn Hảo

📝 Phiên Bản Cơ Bản

⚡ Phiên Bản Tối Ưu - O(√n)

🚀 Thuật Toán Siêu Tối Ưu - Mersenne Primes

📊 Phân Tích Chi Tiết & Visualization

📖 Hướng Dẫn Sử Dụng

🎯 Cách Sử Dụng Ứng Dụng

🔍 Hướng Dẫn Mô Phỏng

💡 Mẹo Sử Dụng

🌐 Tương Thích

🔧 Tùy Chỉnh

📋 Nhật Ký Kiểm Tra

Related Posts

Post a Comment

Không có nhận xét nào

Bài đăng phổ biến

Liên hệ với chúng tôi