PrepBro
← Назад к вопросам

Разложение на простые множители

1.3 Junior🔥 121 комментариев
#Python Core

Условие

Напишите функцию, которая раскладывает число на простые множители.

Пример

factorize(12) → [2, 2, 3] factorize(100) → [2, 2, 5, 5] factorize(17) → [17]

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Разложение на простые множители

Описание

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

Решение 1: Базовый подход (пробное деление)

def factorize(n):
    """Раскладывает число на простые множители."""
    factors = []
    
    while n % 2 == 0:
        factors.append(2)
        n = n // 2
    
    divisor = 3
    while divisor * divisor <= n:
        while n % divisor == 0:
            factors.append(divisor)
            n = n // divisor
        divisor += 2
    
    if n > 1:
        factors.append(n)
    
    return factors

print(factorize(12))   # [2, 2, 3]
print(factorize(100))  # [2, 2, 5, 5]
print(factorize(17))   # [17]

Временная сложность: O(√n) в худшем случае.

Решение 2: Оптимизированное пробное деление

def factorize(n):
    """Оптимизированная версия с проверкой до √n."""
    if n < 2:
        return []
    
    factors = []
    
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += 2
    
    if n > 1:
        factors.append(n)
    
    return factors

Решение 3: Рекурсивный подход

def factorize(n, divisor=2):
    """Рекурсивное разложение на множители."""
    if n < 2:
        return []
    
    if divisor * divisor > n:
        return [n]
    
    if n % divisor == 0:
        return [divisor] + factorize(n // divisor, divisor)
    
    return factorize(n, divisor + 1)

Решение 4: Со словарём для подсчёта множителей

def factorize_dict(n):
    """Возвращает множители в виде словаря."""
    factors = {}
    divisor = 2
    
    while divisor * divisor <= n:
        while n % divisor == 0:
            factors[divisor] = factors.get(divisor, 0) + 1
            n //= divisor
        divisor += 1
    
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    
    return factors

Рекомендуемое решение для интервью

def factorize(n: int) -> list[int]:
    """Раскладывает число на простые множители за O(√n) время."""
    if n < 2:
        return []
    
    factors = []
    
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    
    divisor = 3
    while divisor * divisor <= n:
        while n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        divisor += 2
    
    if n > 1:
        factors.append(n)
    
    return factors

Это решение демонстрирует понимание алгоритма и имеет оптимальную временную сложность O(√n), что является стандартом для решения этой задачи на интервью.

Похожие вопросы