Мной было проверено, что он быстрее двух самых быстрых способов поиска делителей числа: поиск до корня и разложение числа на простые множители с последующим их перебором.
Как он работает:
Раскладывает число на простые множители
Идёт по списку простых множителей (
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