алгоритм поиска всех делителей числа
День! решая задачу пришлось найти в сети алгоритм поиска всех делителей числа. ну то есть для восьми надо выдать [1,2,4,8], а не [2,2,2] — список делителей. Я переписал этот алгоритм наново, прошу «старших товарищей» подсказать как улучшить. Если есть время ))
def divisorss(n): from collections import Counter ls = get_ls(n) # for n=1568 -> ls = [2, 2, 2, 2, 2, 7, 7] pairs = dict(Counter(ls)) # from itertools import product, starmap from operator import mul from functools import reduce # список всех различных делитей числа bases = [b for b in pairs.keys()] # [2, 7] # список степеней, в которые возводятся уникальные делители для получения числа powers = [[i for i in range(k+1)] for k in pairs.values()] # генерирование всех наборов для получения делителей исходного числа multi = product(*powers) # сцепка списка оснований с возможными вариантами степеней wrk = (zip(bases,power) for power in multi) # наборы чисел, которые нужно перемножить для получения делителя rezzz = (starmap( pow, row) for row in wrk) # возвращение списка всех делителей return [reduce(mul,i) for i in rezzz] например divisorss(1568) возвращает [1, 7, 49, 2, 14, 98, 4, 28, 196, 8, 56, 392, 16, 112, 784, 32, 224, 1568] Функция get_ls(n) дает соответственно список разложения числа на произведение делителей например такая:
def get_ls(n): """Разложить число на множители""" #result = [1] result = [] i = 2 while i*i 1: result.append(n) return result что можно улучшить?
Ну например, что лучше — reduce из functools или accumulate из itertools. Ну и вообще по алгоритму. Понятно, что улучшения типа
return [reduce(mul,i) for i in (starmap(pow, row) for row in (zip(bases,power) for power in product(*powers)))] Делители числа
Делитель — это число, на которое нацело делится делимое. У делимого может быть один или несколько делителей, найти их все можно с помощью простого алгоритма, который без проблем реализуется на Python 3.
Нахождение делителей числа
С практической точки зрения будет полезно, если программа на Python не только будет находить делители числа, искать их сумму, определять минимальный и максимальный, а также простые делители.
Каждая подзадача так или иначе связана с предыдущей, поэтому код последующей программы — это немного модернизированный код предыдущей. Кроме того, весь функционал при необходимости можно объединить в одной программе.
Алгоритм нахождения очень простой. В цикле перебираются значения от делимого минус единица до двух включительно. Если делимое нацело делится на текущее значение, то оно является делителем.
Пользователь вводит целое число, делителей которого будет искать программа, тогда код выглядит так:
numb = int(input("Введите целое число: ")) print("Результат:", end = " ") for i in range(numb - 1, 1, -1): if (numb % i == 0): print(i, end = " ") Например, пользователь ввёл число 625. Программа начинает цикл со значения 624, в цикле проверяется, делится ли нацело 625 на 624, затем цикл переходит на следующую итерацию и работает уже с числом 623 и так до двух. Таким образом, вывод программы будет следующим:
Введите целое число: 625 Результат: 125 25 5
Простые делители числа
Простой делитель — это делитель, который делится только на единицу и самого себя. Для нахождения простых делителей с помощью Python нужно немного модернизировать программу, добавив в неё дополнительный цикл for и переменную счётчик.
Программа построена по следующему алгоритму:
- Обнулить счётчик.
- В цикле искать делители.
- Если найден, искать во вложенном цикле его делители. Это для того, чтобы определить: является ли он простым.
- Если найден, увеличить счётчик.
- Если счётчик равен нулю, то число простое и надо вывести значение делителя в консоль.
- Перейти на следующую итерацию внешнего цикла.
Цикл теперь выглядит так:
numb = int(input("Введите целое число: ")) print("Простые:", end = " ") for i in range(numb - 1, 1, -1): is_simple = 0 # Счётчик if (numb % i == 0): for j in range(i - 1, 1, -1): if (i % j == 0): is_simple = is_simple + 1 # Увеличиваем, если находим делитель if (is_simple == 0): # Если делителей не было найдено, выводим print(i, end = " ") Понятно, что если значение счётчика больше нуля — то число точно не простое. Можно оптимизировать немного код и сразу завершать вложенный цикл после увеличения счётчика. Для этого можно воспользоваться оператором break в условном операторе, находящемся во вложенном цикле.
Результат работы программы:
Введите целое число: 63 Простые: 7 3
Делители расположены в порядке убывания. И если надо вывести только самый большой простой делитель с помощью Python, то можно после того, как выведется первое число, воспользоваться оператором break для выхода из цикла.
Сумма делителей
Для того чтобы найти сумму всех делителей числа с помощью Python, достаточно добавить в начальную программу переменную, к которой в цикле будет прибавляться каждый найденный делитель.
Код программы:
numb = int(input("Введите целое число: ")) sum_of_dividers = 0 for i in range(numb - 1, 1, -1): if (numb % i == 0): sum_of_dividers += i print("Сумма:", sum_of_dividers) Результат выполнения кода:
Введите целое число: 63 Сумма: 40
Количество делителей
Этот вариант программы также лишь незначительно отличается от изначального. Для подсчёта делителей нужно ввести переменную-счётчик, к которой будет прибавляться единица каждый раз, когда условие « numb % i == 0 » будет выполняться.
numb = int(input("Введите целое число: ")) count_of_dividers = 0 for i in range(numb - 1, 1, -1): if (numb % i == 0): count_of_dividers += 1 print("Количество равно:", count_of_dividers) Результаты выполнения программы:
Введите целое число: 63 Количество равно: 4
Максимальный и минимальный делитель
Для нахождения минимального и максимального делителя в код на Python нужно добавить две переменные: min_divider и max_divider . В цикле делитель будет сравниваться со значением этих переменных и, если необходимо, записываться в них.
Код программы:
numb = int(input("Введите целое число: ")) min_divider = numb max_divider = 1 for i in range(numb - 1, 1, -1): if (numb % i == 0): if (min_divider > i): min_divider = i if (max_divider < i): max_divider = i print("Минимальный равен:", min_divider) print("Максимальный равен:", max_divider) Результат выполнения:
Введите целое число: 63 Минимальный равен: 3 Максимальный равен: 21
Нахождение наименьшего и наибольшего делителя, подсчёт суммы делителей и их количества можно объединить в одну программу на Python. Это не должно вызвать каких-либо проблем или конфликтов, потому что программа работает с 4 независимыми переменными.
Найти все делители натурального числа
Найти все делители натурального числа N.
Найти все делители натурального числа N.
Зная простые делители числа и их количество, найти все делители числа
Добрый вечер. Есть задача: зная простые делители числа и их количество, найти все делители числа.
Найти все совершенные числа, меньшие данного натурального числа n
Натуральное число называется совершенным, если оно равно сумме всех своих делителей, не равных.
Найти все простые числа, меньшие данного натурального числа
Простые числа на миллион долларов Точная оценка количества простых чисел, меньших данного числа.
k = int(input()) n = 1 r = [] while n k: if k % n == 0: r.append(n) n = n + 1 print(r)
>>> n = 128 >>> d = [ x for x in range(1, n // 2 + 1) if n % x == 0 ] >>> d [1, 2, 4, 8, 16, 32, 64]
def dividers(n): r=[] i=2 while(i*in): if n%i==0: r=r+[i] k=n//i if k != i: r=r+[k] return r
Сообщение от easybudda 
Сообщение от Infeeqs
def dividers(n): r=[] i=2 while(i*in): if n%i==0: r=r+[i] k=n//i if k != i: r=r+[k] return r
Спасибо, но код не отлажен, зацикливание, cкорее всего потеряно изменение i.
Добавлено через 11 минут
easybudda,
спасибо!
Осталось чуть-чуть:
n = 128 d = [x for x in range (1, n // 2 + 1) if n % x == 0] + [n] print (d)
Сообщение от MSP_cyber
1 2 3 4 5 6 7 8 9 10 11 12 13
def dividers(n): r=[] i=2 while(i*in): if n%i==0: r=r+[i] k=n//i if k != i: r=r+[k] i+=1 return r print(dividers(300))
1 2 3 4 5 6 7 8 9 10 11 12 13
def dividers(n): r=[] i=2 while(i*in): if n%i==0: r=r+[i] k=n//i if k != i: r=r+[k] i+=1 return r print(dividers(300))
Найдены не все делители: нет 1 и нет самого n 🙁
Должен и вправду работать быстрее, а как посчитать время? Не могу найти библиотеку time, чтобы, потом, сравнивая, запустить для какого-нибудь громадного числа типа 12345678901234567890.
Добавлено через 33 минуты
А кто-нибудь знаком с методом факторизации? Где-то краем глаза я видел, что вообще будут делители находиться тогда молниеносно.
Добавлено через 1 час 4 минуты
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
# MSP, 27.03.20, 16:28 # MSP, 28.03.20, 17:39 # TASK # Найти все делители данного натурального числа N. from datetime import datetime # 1-e решение N = int (input ('\nВведите натуральное число: ')) # d - делитель числа start_time = datetime.now () for d in range (1, N // 2 + 1) : if N % d == 0 : print (d, ' ', sep = '', end = '') print (N) end_time = datetime.now () print ('time: ', end_time - start_time) # 2-е решение N = int (input ('\nВведите натуральное число: ')) # список делителей start_time = datetime.now () D = [d for d in range (1, N // 2 + 1) if N % d == 0] + [N] print (D) end_time = datetime.now () print ('time: ', end_time - start_time) # 3-e решение start_time = datetime.now () def dividers (N) : D = [1] # список делителей d = 2 # делитель while (d * d N) : if N % d == 0 : D = D + [d] d_new = N // d if d_new != d : D = D + [d_new] # следующий делитель d += 1 D += [N] D.sort () return D print (dividers (int (input ('\nВведите натуральное число: ')))) end_time = datetime.now () print ('time: ', end_time - start_time)
Введите натуральное число: 144
1 2 3 4 6 8 9 12 16 18 24 36 48 72 144
time: 0:00:00.073834
Введите натуральное число: 144
[1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144]
time: 0:00:00.008067
Введите натуральное число: 144
[1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144]
time: 0:00:02.664169
Как видим, третий алгоритм работает медленнее всех. А самый быстрый - второй.
Получается так, что генераторы списка с условием работают быстро!