Мной было проверено, что он быстрее двух самых быстрых способов поиска делителей числа: поиск до корня и разложение числа на простые множители с последующим их перебором.
Как он работает:
Раскладывает число на простые множители
Идёт по списку простых множителей (
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Комментарии (22)
xi-tauw
14.10.2024 18:21Посмотрели бы для чего используется разложение на множители. Я самым частым вариантом задачи встречаю атаку на RSA - найти разложение числа N=pq, где p и q - простые. Чем ваш способ поможет?
Да и вообще, чем ваш способ отличается от решета Эратосфена?
RodionGork
14.10.2024 18:21Заголовок звучит так будто Вы собрались перевернуть мир криптографии.
На деле похоже речь идёт о школьных упражнениях на Питоне. Извините за прямоту, но так делать не надо. Старайтесь чтобы заголовок соответствовал содержанию и не производил фальшивых сенсаций.
Ну и в целом школьная домашка - не совсем контент для хабра.
artptr86
14.10.2024 18:21Логично, что mydiv отрабатывает очень шустро. Ведь там первым этапом идёт факторизация, а выбранные «огромные» тестовые числа являются степенями 10, то есть состоят из простых делителей 2 и 5, отчего факторизация проходит за O(log N). Последующему циклу, который находит все комбинации простых множителей, приходится при этом оперировать небольшим массивом из 2*lg(n) элементов, то есть максимум 100 при n=10^50. При этом sqrtdiv честно делает sqrt(N) итераций, а prchoosediv хоть и факторизует число, но оперирует строками, а это ужасно неоптимально.
Тем не менее я не поленился и проверил работу алгоритмов на других значениях:
10000000011 = 10**10+11 mydiv: 0.0008652210235595703 sqrtdiv: 0.011649847030639648 prchoosediv: 0.000293731689453125 999999999999943 = 10**15-57 mydiv: 0.06576704978942871 sqrtdiv: 1.0241758823394775 prchoosediv: 0.025871992111206055 1000000000000157 = 10**15+157 mydiv: 0.004744768142700195 sqrtdiv: 1.0612590312957764 prchoosediv: 0.0011668205261230469 621993868801161359 = 907 * 911 * 919 * 929 * 937 * 941 mydiv: 0.0004470348358154297 sqrtdiv: 25.041913747787476 prchoosediv: 0.00017499923706054688Легко видеть, что даже неоптимальная реализация prchoosediv примерно в 3 раза быстрее, чем (неоптимальная) реализация авторского алгоритма.
Deosis
14.10.2024 18:21Пусть попробует найти разложение такого числа:
RSA-129 = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
ответ
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577
× 32769132993266709549961988190834461413177642967992942539798288533А за разложение этого числа вообще предлагают солидный приз:
RSA-2048 = 2519590847565789349402718324004839857142928212620403202777713783604366202070 7595556264018525880784406918290641249515082189298559149176184502808489120072 8449926873928072877767359714183472702618963750149718246911650776133798590957 0009733045974880842840179742910064245869181719511874612151517265463228221686 9987549182422433637259085141865462043576798423387184774447920739934236584823 8242811981638150106748104516603773060562016196762561338441436038339044149526 3443219011465754445417842402092461651572335077870774981712577246796292638635 6373289912154831438167899885040445364023527381951378636564391212010397122822 120720357
VBDUnit
14.10.2024 18:21Интересно, когда наступит момент, что пропуск подобного числа через жирную нейросеть даст результат быстрее, чем перебор.
Идея в том, что такая сеть может выявить очень неочевидные корреляции, которые может даже и не формулируемы на человеческом языке, но которые дают возможность раскладывать вот такое вот на простые множители за адекватное время.
Akorabelnikov
14.10.2024 18:21Как математик и ML инженер уверенно заявляю, текущие подходы в нейронках оперируют приблизительными значениями (float point), и big int math прикрутить не видится (пока) разумным
VBDUnit
14.10.2024 18:21Моя мысль в том, что мы не пытаемся запустить big int math на нейронке, то есть не повторяем паттерны человеческого мышления даже на базовому уровне (вплоть до концепции чисел, математики и прочего), не копируем эту логику и воплощение этой логики в алгоритмах.
Мы берём саму задачу и заставляем эту штуку саму найти нужные способы решения. И тогда есть вероятность, что она выявит какой‑то путь, который непонятен нашему мышлению, и, возможно неформулируем вообще на человеческих языках (включая математику) и даже не подлежит какому‑либо осмыслению, то есть для человеческого мозга этот путь будет выглядеть как хаотичные действия, но этот путь будет решать задачу качественно.
DeepFake же не просчитывает распознавание лиц и рендеринг теней и подповерхностного рассеивания для реалистичной замены этих лиц так, как это делает написанный человеком алгоритм со всякими треугольниками и трасировками лучей. Но при этом справляется лучше, чем если это будут делать 3D‑моделеры (вспомним Трон: Наследие). И волосы рендерит с физикой.
Вот я думаю, что вот это вот может простираться дальше графики. Что те концепции, которые мы осмысляем нашим абстрактным мышлением (в том числе «числа», «вычисления» и прочее), могут быть «осмыслены» этим «думающим» объектом в иной, недоступной нам форме, но такой, в которой решение этих сложных задач (как разложение длинных чисел на простые множетели) окажется намного проще и быстрее.
Когда кошка прыгает на стул, она расчитывает параболическую траекторию, но при этом неспособна понять концепцию «параболы» и «траектории». Но задачу решает. Так и тут — возможно, для разложения на множители этой штуке даже «числа» понимать не нужно.
Guestishe
14.10.2024 18:21Нейронки обычно устроены по принципу обработки паттернов одинакового размера. Они не могут масштабировать свой вход. Именно потому человеческий мозг прибегает к разделению задачи на части и логике.
NikkiG
14.10.2024 18:21Вопрос правильной токенизации. Картинки или текст любого размера ты же можешь ей скормить
lovermann
14.10.2024 18:21Если внимательно прочитать статью, то будет ясно, что, возможно, речь идёт о самом быстром способе среди учеников своей группы. Просто автор забыл это добавить, но точно предполагал.
qid00000000
14.10.2024 18:21Не буду как Очередной комментатор издеваться над автором, но добавлю пару слов - посыл хороший, жирный плюс за то, что не побоялся быть высмеянным и интерес к теме. Желаю сохранить все выше.
А теперь должна дёгтя. Есть такое понятие, как научный подход и его не спроста нужно придерживаться (нужно исследовать, что вы не изобретаете велосипед и то, что вы используете - актуально). До нас было много дяденек и тётенек, которые умнее нас и имеют большие ресурсы для, разных исследований, поэтому мы не изобретаем велосипеды заново, а используем те, что уже есть. (В целом, умные дяденьки и тётеньки, не смогли бы тоже многого достичь, если бы не стояли на плечах предшественников).
audiserg
Нобелевскую этому парню!
blik13
Филдсовку тогда уж
LavaLava
Раз python то Нобелевскую по биологии
А мы точно не зря смеемся? Вдруг работает быстрее стандартных средств?
sshikov
А где вы тут увидели стандартные средства? Автор измеряет три своих реализации. Первое очевидное предположение - что все измерения неверные. Второе почти столь же очевидное предположение - что две других реализации написаны не оптимально.
Третье очевидное предположение - а откуда мы вообще знаем, что реализации дают верные результаты?
blik13
Я совсем не математик и не уверен полностью, но такие штуки(с категоричными заявлениями типа самый быстрый) обычно доказываются в общем виде. Ведь не доказав это математически, вы максимум можете сказать что это самый быстрый способ, который известен вам на данный момент. Причем автор вполне может быть прав и это действительно самый быстрый способ из возможных. Это, конечно, душнилово, но к такому быстро приучаешся имея даже очень небольшой опыт с научными статьями.