Задачи на числа: практикум по Python

Расширенные примеры и редкие подходы

Ниже представлены более сложные реализации и неочевидные решения для тех же задач.

1. Проверка простоты: вероятностный тест Миллера - Рабина

Для больших чисел (сотни цифр) детерминированный перебор неприменим. Тест Миллера - Рабина даёт высокую вероятность правильного ответа.

import random

def miller_rabin(n, k=5):
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0:
        return False
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# Пример использования
print(miller_rabin(1000000007))  # True (простое)
print(miller_rabin(1000000009))  # True
print(miller_rabin(1000000011))  # False

True
True
False

2. Числа Армстронга произвольной длины с использованием pow для больших степеней

Для чисел с большим количеством цифр можно использовать функцию pow с модулем, чтобы избежать гигантских чисел, если нужно только сравнение.

def is_armstrong_large(n):
    s = str(n)
    p = len(s)
    # Если p > 60, то даже pow без модуля приведёт к огромному значению, но Python справляется.
    # Для ускорения можно использовать pow(d, p, 10**p) - но это меняет логику.
    return n == sum(pow(int(d), p) for d in s)

# Пример: 10-значное число Армстронга (их всего 4)
print(is_armstrong_large(4679307774))  # True

True

3. Факториал с мемоизацией (кэширование)

Если требуется многократно вычислять факториалы для разных n, эффективно использовать декоратор lru_cache.

from functools import lru_cache

@lru_cache(maxsize=None)
def factorial_memo(n):
    if n < 0:
        raise ValueError("Factorial not defined for negative numbers")
    return 1 if n <= 1 else n * factorial_memo(n - 1)

# Примеры
print(factorial_memo(10))
print(factorial_memo(20))
print(factorial_memo.cache_info())

3628800
2432902008176640000
CacheInfo(hits=1, misses=21, maxsize=None, currsize=21)

4. НОД: бинарный алгоритм (алгоритм Стейна)

Этот алгоритм использует только сдвиги и вычитания, что может быть быстрее на очень больших числах.

def gcd_binary(a, b):
    a, b = abs(a), abs(b)
    if a == 0:
        return b
    if b == 0:
        return a
    shift = 0
    while ((a | b) & 1) == 0:
        a >>= 1
        b >>= 1
        shift += 1
    while (a & 1) == 0:
        a >>= 1
    while b != 0:
        while (b & 1) == 0:
            b >>= 1
        if a > b:
            a, b = b, a
        b -= a
    return a << shift

# Пример
print(gcd_binary(123456789, 987654321))  # 9
print(gcd_binary(-121, 11))             # 11

9
11

5. НОК через НОД

Стандартная формула: lcm(a,b) = abs(a*b) // gcd(a,b).

def lcm(a, b):
    return abs(a * b) // gcd(a, b)  # gcd из предыдущего примера

print(lcm(12, 18))  # 36
print(lcm(7, 13))   # 91

36
91

6. Решето Эратосфена для генерации списка простых чисел до N

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return [num for num, is_p in enumerate(is_prime) if is_p]

primes = sieve_of_eratosthenes(50)
print(primes)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]