Аз го виждам по малко по-различне начин:
1. започвам от sqrt(N) и търся < просто число
2. от остатъка аналогично следващото и така надолу.
Многовариантността може да се провери с корен 3, и нагоре
Според мен лоша идея е това със sqrt(N) и надолу. Има една теорема според която вероятността случайно число <N да е просто, клони към 1/ln(N). Това ми се вижда прекалено много, предвид че ние ще трябва да пазим информация за степените на всяко просто число. Сметката набързо е че между 1 и 2**64 имаме 4.158285343076351e+17
прости числа, които трябва да се представят и това нещо заклевам се ще изяде далеч повече памет, отколкото самото число N представено по "нормалния" начин.
Затова според мен броя на простите числа, които ще използваме трябва да е далеч, далеч по-малък. Това означава по-високи степени и съответно повече място за пазенето им, но това е с порядъци по-пестеливо, отколкото да си позволим да пазим степените (или липсата им) на голям брой прости числа.
Цялата работа и това което доста ме кара да се съмнявам във въпросната чудодейна схема е че на първо четене, каквато и основа за степенуване да изберем по-голяма от 2, би трябвало да сме на далавера....поне така изглежда, обаче нещо ме гризе отвътре че нещата не са толкова прости и нищо не идва ей така отнякъде. Понеже аз поне съм тъп и не мога да докажа обратното, а могат да се дадат лесно примери, където буквално такова представяне би сгазило брутално всеки масово използван алгоритъм за компресия, нещата очевидно са забавни. Ако изключим проблемите при намирането на въпросните степени и според мен това въобще не е толкова тривиална задача, но да речем че има решение, остава въпросът доколко вероятни са въпросните примери и дали в масовия случай такова представяне на входните данни няма да е далеч по-неефективно. За съжаление нито съм достатъчно голяма глава, а и съм одъртял и изпростял и ме мързи да мисля толкова по въпроса. Та вариантът според мен е да се изтества цялата постановка с достатъчно малки числа N и да се измисли някакъв на първо четене работещ, не казано много велик и оптимален алгоритъм за откриването на корените. В процесът според мен ще излязат наяве евентуалните теоретични драми.
