Оптимизиране на алгоритъм за разлагане на прости числа

Следното по-долу е алгоритъм, който намира разлагането на прости множители за дадено число N. Чудя се дали има някакви начини да направя това по-бързо, като използвам ОГРОМНИ числа. Говоря като 20-35 цифрени числа. Искам да се опитам да ги накарам да вървят възможно най-бързо. Някакви идеи?

import time

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    divisor = 2        
    while n > 1:        
        while n % divisor == 0:
            factors.append(divisor)
            n /= divisor          
        divisor = divisor + 1
        if divisor*divisor > n:
            if n > 1: 
                factors.append(n)
            break
    return factors

#HUGE NUMBERS GO IN HERE!
start_time = time.time()
my_factors = prime_factors(15227063669158801)
end_time = time.time()
print my_factors
print "It took ", end_time-start_time, " seconds."

python optimization factorization
person Binka    schedule 03.04.2014    source източник
comment
Колко време получавате за горния номер?   -  person sshashank124    schedule 03.04.2014
comment
По-малко от секунда. Но за някои 20-цифрени числа и повече отнема повече от 30 секунди!   -  person Binka    schedule 03.04.2014
comment
вместо да увеличавате divisor с 1 всеки път, можете вместо това да итерирате простите числа.   -  person desired login    schedule 03.04.2014
comment
stackoverflow.com/questions/12268526 /   -  person user1474424    schedule 03.04.2014
comment
На първо място, избягвайте добавянето. Това отнема време, защото всеки път, когато добавяте към списък, той трябва да бъде преразпределен в паметта, което отнема време. Това може да се реши чрез предварително разпределяне на списък към определен размер (вярвам, че публикацията по-горе засяга това) - ще трябва да разберете максималните прости фактори в число. Също така, вместо да увеличавате делителя с едно, задайте го на следващото просто число.   -  person Jacob Kudria    schedule 03.04.2014
comment
Добра идея, благодаря ти Джейкъб.   -  person Binka    schedule 03.04.2014
comment
@JacobKudria: През повечето време добавянето към списък не изисква преоразмеряване. Размерът на списъка се мащабира по такъв начин, че добавянето на N елемента отнема общо време O(N). Предварителното разпределение понякога може да спести време, но не много.   -  person user2357112 supports Monica    schedule 03.04.2014
comment
rosettacode.org/wiki/Prime_decomposition#Python   -  person Z boson    schedule 03.04.2014
comment
@ user2357112 Благодаря. Винаги са ми казвали, че трябва да разпределя предварително, но ако това не спестява много време, тогава...   -  person Jacob Kudria    schedule 03.04.2014

Отговори (4)


arrow_upward
1
arrow_downward

Вашият алгоритъм е пробно деление, което има времева сложност O(sqrt(n)). Можете да подобрите алгоритъма си, като използвате само 2 и нечетните числа като пробни делители или дори по-добре, като използвате само прости числа като пробни делители, но времевата сложност ще остане O(sqrt(n)).

За да вървите по-бързо, имате нужда от по-добър алгоритъм. Опитайте тази:

def factor(n, c):
    f = lambda(x): (x*x+c) % n
    t, h, d = 2, 2, 1
    while d == 1:
        t = f(t); h = f(f(h)); d = gcd(t-h, n)
    if d == n:
        return factor(n, c+1)
    return d

За да се обадя на вашия номер, кажете

print factor(15227063669158801, 1)

Това връща (вероятно съставния) коефициент 2090327 почти мигновено. Той използва алгоритъм, наречен алгоритъм rho, изобретен от Джон Полард през 1975 г. Алгоритъмът rho има времева сложност O(sqrt(sqrt(n))), така че е много по-бърз от пробното деление.

Има много други алгоритми за разлагане на цели числа. За числа в диапазона от 20 до 35 цифри, който ви интересува, алгоритъмът за елиптична крива е много подходящ. Той трябва да разлага числа от този размер за не повече от няколко секунди. Друг алгоритъм, който е много подходящ за такива числа, особено тези, които са полупрости (имат точно два прости множителя), е SQUFOF.

Ако се интересувате от програмиране с прости числа, скромно препоръчвам това есе в моя блог. Когато приключите с това, други записи в моя блог говорят за факторизация на елиптична крива и SQUFOF, както и различни други още по-мощни методи за факторизиране на все по-големи цели числа.

person user448810    schedule 04.04.2014
comment
TD на прости числа е ~ 2sqrt(n)/log(n) според мен. - person Will Ness; 06.04.2014
comment
Мисля, че сте прав, но в диапазона от n, където пробното деление има смисъл, коефициентът на log(n) няма голямо значение, особено когато получавате само половината от него, така че има някакъв смисъл да мислите за пробно деление като O(sqrt(n)) алгоритъм, без значение как го прилагате (коефициенти, 2,3,5 колело, прости числа). Поне аз винаги го правя. - person user448810; 07.04.2014
comment
емпирично получавам само половината от тази половина, но все още се забелязва ускоряване от 6,8x :) (TD факторизиране на прости числа срещу коефициенти, отстъпка от генерирането на прости числа). А за още 1 цифра е 7,2x. Така че го смятам за малко по-добър от sqrt(n). Много по-добре би означавало ускоряване на хиляди или милиони разбира се. Това означава, че мога да използвам TD за още около две цифри, с прости числа. -- (Също така пробвах вашия код с просто число... :) ) - person Will Ness; 07.04.2014
comment
@WIllNess: (по отношение на вашия коментар в скоби) Ако се опитате да разложите на множители просто число, вие заслужавате каквото и да получите. - person user448810; 07.04.2014
comment
Но не бях предупреден!! :) :) - person Will Ness; 08.04.2014

arrow_upward
0
arrow_downward

Например, избройте всички прости фактори за число 100.

  • Проверка 2 дали е едно от факторизациите или не. И тогава 2 ‹ 2*c ‹= 100 може да бъде премахнато. Пр. 4, 6, 8, ... 98
  • Проверка 3 дали е едно от факторизациите или не. И тогава 3 ‹ 2*d ‹= 100 може да бъде премахнато. Пр. 9, 12, ... 99
  • 4 е премахнат от възможния набор.
  • Поставете отметка на 5 и след това 10, 15, 20, ..., 100 се премахват.
  • 6 е премахнат.
  • Проверете 7, .... ....
person AechoLiu    schedule 03.04.2014

arrow_upward
0
arrow_downward

Изглежда, че няма проверка за делители. Съжалявам, ако греша, но как да разберете дали делителя е прост или не? Вашата променлива на делителя се увеличава с 1 след всеки цикъл, така че предполагам, че ще генерира много съставни числа.

person Lorientas    schedule 04.04.2014

arrow_upward
0
arrow_downward

Никакви оптимизации на този алгоритъм няма да ви позволят да факторизирате 35-цифрени числа поне в общия случай. Причината е, че броят на простите числа до 35 цифри е твърде голям, за да бъде изброен в разумен период от време, да не говорим за опит за разделяне на всеки един. Дори ако човек е склонен да опита, броят на битовете, необходими за съхраняването им, също би бил твърде голям. В този случай ще искате да изберете различен алгоритъм от списъка с алгоритми за факторизация с общо предназначение.

Въпреки това, ако всички прости множители са достатъчно малки (да речем под 10^12 или така), тогава можете да използвате сегментиран Решето на Ератостен или просто намерете онлайн списък с прости числа до някакво практично число (да речем 10^12 или нещо такова) и го използвайте, вместо да се опитвате да изчислите простите числа и да се надявате, че списъкът е достатъчно голям.

person Nuclearman    schedule 04.04.2014