Divisors python что это
Как найти все делители числа в Python
06 марта 2023
Оценки статьи
Еще никто не оценил статью
При работе с числами в 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] Как найти делители числа с помощью функции в Python?
Функция для нахождения делителей целого положительного числа:
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] Python divisors примеры использования
Python divisors — 6 примеров найдено. Это лучшие примеры Python кода для Common.divisors, полученные из open source проектов. Вы можете ставить оценку каждому примеру, чтобы помочь нам улучшить качество примеров.
Related in langs
def distinctPrimeFactors(n): div = divisors(n) div.remove(1) toRemove = set() [toRemove.add(d) for d in div if not isPrime(d)] return div - toRemove
#============================================================================== # Evaluate the sum of all the amicable numbers under 10000. #============================================================================== from Common import divisors total = 0 for a in range(1, 10000): b = sum(divisors(a)) - a if sum(divisors(b)) - b == a and not a == b: total += a print(total)
#=============================================================================== # What is the largest prime factor of the number 600851475143 ? #=============================================================================== from Common import isPrime, divisors print(max([i for i in divisors(600851475143) if isPrime(i)]))
#=============================================================================== # What is the value of the first triangle number to have over five hundred divisors? #=============================================================================== from Common import divisors, trianglenum i = 1 while True: if len(divisors(trianglenum(i))) > 500: break i += 1 print(trianglenum(i))
#=============================================================================== # Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. #=============================================================================== from Common import divisors bound = 28123 abundants = [] [abundants.append(i) for i in range(1, bound) if sum(divisors(i)) - i > i] sums = set() high = 0 length = len(abundants) for i in range(length): high = 0 j = i; while high < bound and j < length: summed = abundants[i] + abundants[j] sums.add(summed) high = summed j += 1 if abundants[i] * 2 >= bound: break print(sum(set(range(1, bound)) - sums))
Помогите оптимизировать алгоритм нахождения делителей
Задумка в том, чтобы когда делитель был найден, программа делила на него число, тем самым, она работала бы быстрее. Но строчка number1 /= i только все портит, так как некоторая часть делителей просто не находится и также не изменяет значение nimber1 в цикле. Помогите пожалуйста(
Отслеживать
задан 14 мая 2020 в 17:10
45 4 4 бронзовых знака
В качестве делителей должны проверяться только числа из dividers?
14 мая 2020 в 17:36
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
from functools import reduce def sieve_of_eratosthenes(n): is_prime = 2 * [False] + (n-1) * [True] p = 2 while (p * p = nfactors: return divisors all_divisors(24) [1, 2, 4, 8, 3, 6, 12, 24] Разложим число на простые множители и создаем все комбинации этих простых множителей.
Пример: Число 24.
Разложение: 24 = 2**3 * 3**1
Возможные степени 2: 2**0 , 2**1 , 2**2 , 2**3
Возможные степени 3: 3**0 , 3**1
Делители:
2**0 * 3**0 1
2**1 * 3**0 2
2**2 * 3**0 4
2**3 * 3**0 8
2**0 * 3**1 3
2**1 * 3**1 6
2**2 * 3**1 12
2**3 * 3**1 24