Совершенное число

Совершенное число

Совершенное число — это натуральное число, которое равно сумме всех своих собственных делителей (всех положительных делителей, кроме самого числа). Например, 6 = 1 + 2 + 3 и 28 = 1 + 2 + 4 + 7 + 14.

Решение 1: Наивный подход O(n)

def is_perfect_number_naive(n: int) -> bool:
    """
    Проверяет, является ли число совершенным.
    Временная сложность: O(n)
    Пространственная сложность: O(1)
    """
    if n <= 1:
        return False
    
    # Вычисляем сумму всех собственных делителей
    divisor_sum = 0
    for i in range(1, n):
        if n % i == 0:
            divisor_sum += i
    
    return divisor_sum == n

# Тестирование
print(is_perfect_number_naive(6))    # True
print(is_perfect_number_naive(28))   # True
print(is_perfect_number_naive(12))   # False
print(is_perfect_number_naive(1))    # False
print(is_perfect_number_naive(496))  # True

Решение 2: Оптимизированный подход O(sqrt(n))

Оптимизация: нужно проверять только делители до sqrt(n).

import math

def is_perfect_number(n: int) -> bool:
    """
    Проверяет, является ли число совершенным.
    Временная сложность: O(sqrt(n))
    Пространственная сложность: O(1)
    """
    if n <= 1:
        return False
    
    divisor_sum = 1  # 1 всегда делитель для n > 1
    
    # Проверяем делители до sqrt(n)
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisor_sum += i
            # Если i и n//i разные, добавляем и n//i
            if i != n // i:
                divisor_sum += n // i
    
    return divisor_sum == n

# Тестирование
print(is_perfect_number(6))    # True
print(is_perfect_number(28))   # True
print(is_perfect_number(12))   # False
print(is_perfect_number(496))  # True
print(is_perfect_number(8128)) # True

Решение 3: С использованием набора делителей

def is_perfect_number_v3(n: int) -> bool:
    """
    Альтернативный подход с явным сбором делителей.
    """
    if n <= 1:
        return False
    
    divisors = set()
    
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    
    # Удаляем само число из множества
    divisors.discard(n)
    
    return sum(divisors) == n

# Тестирование
print(is_perfect_number_v3(6))    # True
print(is_perfect_number_v3(28))   # True
print(is_perfect_number_v3(12))   # False

Анализ сложности

Математический факт

Все известные совершенные числа чётные. Существует связь:

Если 2^p - 1 — простое число (число Мерсенна), то:

N = 2^(p-1) × (2^p - 1) — совершенное число

def find_perfect_numbers_formula(limit: int) -> list:
    """
    Находит совершенные числа, используя формулу Евклида.
    """
    perfect_numbers = []
    
    # Проверяем числа Мерсенна
    for p in range(2, 20):
        mersenne = (2 ** p) - 1
        
        # Проверяем, простое ли число Мерсенна
        if is_prime(mersenne):
            perfect_num = (2 ** (p - 1)) * mersenne
            if perfect_num <= limit:
                perfect_numbers.append(perfect_num)
    
    return perfect_numbers

def is_prime(n: int) -> bool:
    """Простая проверка простоты числа."""
    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

# Находим совершенные числа до 100000
perfect_nums = find_perfect_numbers_formula(100000)
print(perfect_nums)  # [6, 28, 496, 8128]

Полное решение с тестами

def is_perfect_number(n: int) -> bool:
    """
    Проверяет, является ли число совершенным.
    
    Args:
        n: Натуральное число для проверки
    
    Returns:
        True если число совершенное, иначе False
    
    Raises:
        ValueError: Если n < 1
    """
    if n < 1:
        raise ValueError("Число должно быть натуральным (> 0)")
    
    if n <= 1:
        return False
    
    divisor_sum = 1  # 1 всегда делитель
    
    # Проверяем делители до sqrt(n)
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            divisor_sum += i
            # Добавляем парный делитель n // i, если он не равен i
            if i != n // i:
                divisor_sum += n // i
            
            # Ранний выход, если сумма уже больше n
            if divisor_sum > n:
                return False
    
    return divisor_sum == n

# Тестирование
def test_perfect_number():
    # Совершенные числа
    assert is_perfect_number(6) == True
    assert is_perfect_number(28) == True
    assert is_perfect_number(496) == True
    assert is_perfect_number(8128) == True
    
    # Не совершенные числа
    assert is_perfect_number(1) == False
    assert is_perfect_number(12) == False
    assert is_perfect_number(24) == False
    assert is_perfect_number(100) == False
    
    # Граничные случаи
    assert is_perfect_number(2) == False
    assert is_perfect_number(3) == False
    
    print("Все тесты пройдены!")

test_perfect_number()

Известные совершенные числа

# Первые 4 совершенные числа:
perfect_numbers = [6, 28, 496, 8128]

for num in perfect_numbers:
    print(f"\n{num}:")
    
    # Находим делители
    divisors = []
    for i in range(1, num):
        if num % i == 0:
            divisors.append(i)
    
    print(f"  Делители: {divisors}")
    print(f"  Сумма: {' + '.join(map(str, divisors))} = {sum(divisors)}")
    print(f"  Совершенное: {sum(divisors) == num}")

Практическое применение

Совершенные числа используются в:

• Теории чисел — исследование свойств натуральных чисел
• Криптографии — некоторые криптографические алгоритмы
• Задачах оптимизации — в качестве тестовых примеров

Ключевые моменты

1. Оптимизация до O(sqrt(n)) очень важна для больших чисел
2. Ранний выход когда сумма превышает n
3. Правильная обработка парных делителей при проверке до sqrt(n)
4. Входная валидация для некорректных значений
5. Тестирование граничных случаев