Pull to refresh

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

Level of difficultyMedium
Reading time2 min
Views10K

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

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

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

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

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

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

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

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

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

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

Tags:
Hubs:
Total votes 22: ↑7 and ↓15-5
Comments35

Articles