/
Вопросы и ответы
/
Python
/

Как найти делители числа с помощью функции в Python?

Как найти делители числа с помощью функции в Python?

4 года назад

Andrey Moshkov

Ответы

0

Функция для нахождения делителей целого положительного числа:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def get_divisors(number):
    # Чтобы делители в списке не повторялись, собираем их в множество.
    result = {1, number}

    # Перебираем диапазон до number // 2, потому что единственный делитель 
    # больше половины числа - это само число, его мы уже включили в результат.
    # Чтобы половина тоже вошла в диапазон, добавляем к ней 1.
    for divisor in range(2, number // 2  + 1):
      if number % divisor == 0:
          result.add(divisor)

    # функция sorted() сортирует делители по возрастанию и возвращает результат в виде списка
    return sorted(result)


get_divisors(1) # [1]
get_divisors(2) # [1, 2]
get_divisors(11) # [1, 11]
get_divisors(33) # [1, 3, 11, 33]
get_divisors(64) # [1, 2, 4, 8, 16, 32, 64]

4 года назад

Карина Абдуллаева

0

Делитель числа n — число, на которое n делится без остатка. Проверяют остатком от деления %:

1
2
3
4
def divisors(n):
    return [d for d in range(1, n + 1) if n % d == 0]

print(divisors(12))  # [1, 2, 3, 4, 6, 12]

Функция перебирает все числа от 1 до n. Для небольших чисел этого достаточно.

Быстрее: до корня из числа

Делители идут парами: если d делит n, то и n // d делит n. Достаточно проверить числа до √n:

1
2
3
4
5
6
7
8
9
10
11
12
def divisors(n):
    result = []
    d = 1
    while d * d <= n:
        if n % d == 0:
            result.append(d)
            if d != n // d:
                result.append(n // d)
        d += 1
    return sorted(result)

print(divisors(36))  # [1, 2, 3, 4, 6, 9, 12, 18, 36]

Для n = 1 000 000 первый вариант делает миллион проверок, второй — тысячу. Условие d != n // d не даёт дважды добавить корень полного квадрата: у 36 это 6.

Только собственные делители

Без самого числа:

1
print(divisors(12)[:-1])  # [1, 2, 3, 4, 6]

Сумма собственных делителей помогает найти совершенные числа: у 28 она равна 28.

Простое ли число

У простого числа два делителя: 1 и оно само.

1
2
3
4
def is_prime(n):
    return n > 1 and len(divisors(n)) == 2

print(is_prime(13))  # True

Простые множители

1
2
3
4
5
6
7
8
9
10
11
12
13
def prime_factors(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

print(prime_factors(360))  # [2, 2, 2, 3, 3, 5]

Отрицательные числа и ноль

Функции выше рассчитаны на целые n > 0. У нуля делителем будет любое число, кроме нуля. Для отрицательного n найдите делители abs(n).

Функции и циклы разбирают в бесплатном курсе «Основы Python».

10 дней назад

Никита Вихров

+7 800 100 22 47

бесплатно по РФ

+7 495 085 21 62

бесплатно по Москве

108813 г. Москва, вн.тер.г. поселение Московский,
г. Московский, ул. Солнечная, д. 3А, стр. 1, помещ. 20Б/3
ОГРН 1217300010476
ИНН 7325174845