Мной было проверено, что он быстрее двух самых быстрых способов поиска делителей числа: поиск до корня и разложение числа на простые множители с последующим их перебором.
Как он работает:
-
Раскладывает число на простые множители
-
Идёт по списку простых множителей (
i
) и списку всех известных делителей числа (j
):
2.1. Если (простой множитель с индексом i
) * (известный делитель с индексом j
) не встречается в списке известных делителей числа, то в список это значение не добавляется (чтобы каждый раз цикл не проходился по повторяющимся значениям)
2.2. Если простой множитель с индексом i
отсутствует, то он добавляется
-
Добавляет в конце списка делителей числа единицу
-
Возвращает отсортированный список
Реализация (с выше названными способами поиска делителей числа):
import time from math import * import itertools def mydiv(n): # мой способ поиска делителей divs = [] # все делители prdivs = [] # простые делители nownum = n # текущее число, увидите его значение в разложении isPrime = False # в случае, если делителей до корня не нашли, isPrime = True # разложение на простые множители while isPrime == False: isPrime = True for i in itertools.chain([2], range(3, int(nownum ** 0.5) + 1, 2)): if nownum % i == 0: prdivs.append(i) isPrime = False nownum //= i break prdivs.append(nownum) for i in range(len(prdivs)): for j in range(len(divs)): if divs[j] * prdivs[i] not in divs: divs.append(divs[j] * prdivs[i]) if prdivs[i] not in prdivs[0:i]: divs.append(prdivs[i]) divs.append(1) return sorted(set(divs)) # set() нужен, потому что по непонятной мне причине на степенях двойки появляется лишняя единица def sqrtdiv(n): # способ поиска делителей до корня divs = [] for i in range(1, int(n ** 0.5) + 1): if n % i == 0: divs.append(i) divs.append(n // i) return sorted(divs) def prchoosediv(n): # способ поиска делителей разложением числа на простые множители и их перебором divs = [] prdivs = [] nownum = n isPrime = False while isPrime == False: isPrime = True for i in itertools.chain([2], range(3, int(nownum ** 0.5) + 1, 2)): if nownum % i == 0: prdivs.append(i) isPrime = False nownum //= i break prdivs.append(nownum) # здесь я решил использовать бинарную логику num = 1 for i in range(2 ** len(prdivs) - 1): whattomult = bin(num)[2:] # 0b в начале нам не нужно whattomult = "0" * (len(prdivs) - len(whattomult)) + whattomult # вставляем ноли столько раз, чтобы длина строки = длина prdivs mult = 1 for j in range(len(whattomult)): if whattomult[j] == "1": mult *= prdivs[j] if mult not in divs: divs.append(mult) num += 1 divs.append(1) return sorted(divs)
Перед тестами отмечу, что скорость выполнения mydiv()
и prchoosediv()
пропорциональна не n
, а количеству простых делителей n
. И при простом n
все эти функции будут выполняться за одно время.
Тесты:
n = int(input()) start = time.time() mydiv(n) end = time.time() print(f"mydiv: {end - start}") start = time.time() sqrtdiv(n) end = time.time() print(f"sqrtdiv: {end - start}") start = time.time() prchoosediv(n) end = time.time() print(f"prchoosediv: {end - start}")
При n = 360:
mydiv: 0.0 sqrtdiv: 0.0 prchoosediv: 0.0
При n = 1000000:
mydiv: 0.0 sqrtdiv: 0.0 prchoosediv: 0.004986286163330078
При n = 10^10:
mydiv: 0.0 sqrtdiv: 0.00897526741027832 prchoosediv: 2.245990514755249
Отсюда sqrtdiv()
и prchoosediv()
не проверяю.
При n = 10^15:
mydiv: 0.0019936561584472656
При n = 10^50:
mydiv: 0.4697425365447998
ссылка на оригинал статьи https://habr.com/ru/articles/850592/
Добавить комментарий