Каков самый быстрый алгоритм для вычисления всех факторов целого числа?

Question

Я написал этот блок кода, но он потребляет много времени, чтобы вычислить ... Можете ли вы помочь мне найти эффективный способ сделать это?

int tag; 
int* factors(int n) 
{ 
    int a[1000000]; 
    for(int i=1;i<=n/2;i++) 
     if(n%i==0) 
      a[++tag]=i; 
    a[++tag]=n; 
    return(a); 
} 

Этот метод грубой силы очень здоровенный с точки зрения сложности ... Есть ли более целесообразное решение этой проблемы?

Answer 1

До сих пор никто не придумал много более быстрый алгоритм. Это не обязательно означает, что нет никого, поскольку, с другой стороны, также не доказано, что это невозможно сделать намного быстрее.

Одна оптимизация, которую вы, возможно, захотите принять во внимание, состоит в том, что нет необходимости искать до n/2, вы можете уже остановить, когда достигнут sqrt (n).

... и не забудьте выбрать другое место для хранения ваших номеров, если вы действительно хотите вернуть список всех кандидатов, как уже упоминалось в комментарии «chris».

EDIT:

Как я прорекламировали, что существует довольно большое разнообразие алгоритмов доступны, что с точки зрения сложности времени может работать немного быстрее, чем тот, который вы просили об этом может быть указано, чтобы добавить еще несколько слов, чем приведенный выше короткий комментарий.

Хотя кроме самой очевидной возможностью безопасного некоторого времени вычислений, просто запустив цикл с шагом 2 после первого деления его до нечетного числа все еще доступны некоторые другие приемы, я не упомянул их как существенно быстрее в ответе, указанном выше.

Основная причина, повлекшая за собой такое решение, заключалась в том, что, например, сокращение числа итераций в 2 раза кажется большим выигрышем по сравнению с ожидаемым ростом времени выполнения с ростом числа показателей в терминах постоянной становится настолько малой, что в теории сложности даже не будет иметь никакого значения вообще, и оба алгоритма будут иметь (почти) одинаковые временные сложности.

Даже если бы можно было получить постоянный выигрыш в сотнях миллиардов раз времени выполнения исходного алгоритма, все равно не было бы никакой разницы между ними обоими.

Чем больше чисел, тем меньше влияние на любую константу будет такой большой, как вы когда-либо сможете воспроизводить изображения с точки зрения времени выполнения, если она также быстро растет с величиной числа, которое вы адресуете.

Особый барьер с точки зрения временной сложности, который часто рассматривается как граница между практически осуществимым и просто невозможным, - это так называемая операционная среда polynomial.

Это не означает ничего другого, чем даже при том, что во время выполнения может вырасти резко с ростом n еще можно описать этот рост с постоянной показателем k, таким образом, что во время выполнения является то, что вокруг n^k.

С другой стороны, алгоритм без polynomial времени исполнения не может быть измерен каким-либо экспонентом, насколько велика вы можете это сделать.

Чтобы привести пример, почему это различие действительно имеет значение, давайте взглянем на два воображаемых алгоритма. Первый из которых имеет полиномиальное время выполнения, скажем n^10, и еще один говорит об этом со временем выполнения n!.

Хотя для небольших чисел это не кажется плохим, допустим, что n - это всего 10 здесь. Алгоритм принимает 10^10 = 10000000000 единиц времени, а только 3628800 единиц нашего второго алгоритма, похоже, работает даже намного быстрее.

Проблема с нашим алгоритмом 2 заключается в том, что по сравнению с алгоритмом его время выполнения будет значительно расти быстрее. В n=100 вы получаете что-то вроде: 100000000000000000000 для алгоритма один, хотя это уже что-то вроде 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 для алгоритма два.

Нажав границы еще дальше с n=1000, мы получим: алгоритм один на 1000000000000000000000000000000, а наш второй алгоритм займет примерно 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.

Если вы не верите, просто вычислите его самостоятельно. В руководстве bc приведен пример того, как реализовать факториальную функцию.

Но не получайте головокружения при подсчете цифр ... Возможно, было бы интересно узнать, сколько конечных нулей нам нужно было бы добавить до 10, чтобы получить коэффициент, с помощью которого можно умножить возраст нашей Вселенной, чтобы получить такой большой промежуток времени, даже если бы мы измерялись в единицах планковского времени. К сожалению, я не знаю.

Что интересно обо всем, что до сих пор не существует известного алгоритма, который может выполнять факторизацию в polynomial времени.

Как это не только интересная область исследований ИНТ себе практическое невозможность факторизации больших целых чисел также играет важную роль в ключевой алгоритм RSA публичного шифрования, который широко используется в настоящее время, так что почти естественно, имеет уже было много resarch в этой области.

Обнаружение алгоритмов, которые (без нарушения уже упомянутого барьера) запускают sligthly быстрее, чем алгоритм, который вы предполагали.

Как «Jim Balter» alredy, правильно аннотированный в его комментарии, вы можете взглянуть на статью, указанную в ссылке (см.: http://en.wikipedia.org/wiki/Integer_factorization#General-purpose), чтобы взглянуть на методы, которые уже придумали.

В этой статье также упоминается «Jim» может быть еще один интересный ресурс: (см: What is the fastest factorization algorithm?)

Еще одна интересная ссылка, чтобы посмотреть на может быть список победителей факторинг Challange RSA за последние годы в как-то получить представление о том, где граница между допустимыми и почти невозможными может оказаться сегодня. (http://en.wikipedia.org/wiki/RSA_Factoring_Challenge)