Я создал самый быстрый способ поиска делителей числа

Мной было проверено, что он быстрее двух самых быстрых способов поиска делителей числа: поиск до корня и разложение числа на простые множители с последующим их перебором.

Как он работает:

1. Раскладывает число на простые множители

2. Идёт по списку простых множителей (i) и списку всех известных делителей числа (j):

2.1. Если (простой множитель с индексом i) * (известный делитель с индексом j) не встречается в списке известных делителей числа, то в список это значение не добавляется (чтобы каждый раз цикл не проходился по повторяющимся значениям)

2.2. Если простой множитель с индексом i отсутствует, то он добавляется

3. Добавляет в конце списка делителей числа единицу

4. Возвращает отсортированный список

Реализация (с выше названными способами поиска делителей числа):

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