При работе с числами в Python часто требуется находить все делители заданного числа. Нахождение всех делителей может быть полезно для решения различных задач, таких как нахождение наибольшего общего делителя, проверка числа на простоту и т.д. В этой статье мы рассмотрим несколько способов нахождения всех делителей числа в Python.

Простой подход нахождения делителей

Простой подход заключается в переборе всех чисел от 1 до заданного числа n и проверке каждого числа на деление на n. Код для нахождения всех делителей числа n с помощью наивного подхода будет выглядеть следующим образом:

def find_divisors(n):
    divisors = []
    for i in range(1, n+1):
        if n % i == 0:
            divisors.append(i)
    return divisors

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

Более оптимальный подход нахождения делителей

Второй способ нахождения всех делителей заключается в переборе только чисел от 1 до корня из заданного числа n. Если мы нашли делитель i, то мы также можем добавить в список делителей n/i. Код для нахождения всех делителей числа n с помощью более оптимального подхода будет выглядеть следующим образом:

import math

def find_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return divisors

Этот код работает корректно и имеет сложность времени O(sqrt(n)), что гораздо лучше, чем простой подход.

Решето Эратосфена в Python

Третий способ нахождения всех делителей заключается в нахождении всех простых делителей заданного числа и их степеней. Для нахождения простых делителей мы можем использовать Решето Эратосфена.

Затем мы будем проверять, на какие степени делятся каждый из простых делителей. Код для нахождения всех делителей числа n с помощью Решета Эратосфена будет выглядеть следующим образом:

def sieve_of_eratosthenes(n):
    primes = [True for i in range(n+1)]
    p = 2
    while p**2 <= n:
        if primes[p]:
            for i in range(p**2, n+1, p):
                primes[i] = False
        p += 1
    return [i for i in range(2, n+1) if primes[i]]

def prime_factors(n):
    factors = []
    primes = sieve_of_eratosthenes(n)
    for p in primes:
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors

Эти функции могут быть использованы для нахождения делителей любого целого числа. Например, для числа 12 результат работы этих функций будет таким:

>>> find_divisors(12)
[1, 2, 3, 4, 6, 12]

>>> prime_factors(12)
[2, 2, 3]