[python] Faktorizace

[Pavel Kosina]

Jakub Vojáček napsal(a), dne 12.12.2008 16:34:
> Dobrý den,
>
> Vyvýjím jednu aplikaci a potřebuji, aby daná aplikace uměla rozložit číslo na součin prvočísel (prvočíselný rozklad). Naprogramovat nějaký základní algoritmus není problém, ale problém nastane, pokud do algoritmu zadám nějaké větší číslo (např. 4848484848484841178813). 
> Mému algoritmu toto číslo trvá dost dlouho, ale například na této stránce dostanu výsledek takřtka okamžitě: http://www.numberempire.com/primenumbers.php
>
> Jaký algoritmus byste mi doporučili používat? Na menší čísla se dá použít faktorizace dělením:
>
> def faktorizace_delenim(i):
>     prvocisla = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>     seznam=[]
>     cislo = 0
>     while len(prvocisla) != cislo:
>         if i%prvocisla[cislo] == 0:
>             seznam.append(prvocisla[cislo])
>             i = i/prvocisla[cislo]
>         else:
>             cislo = cislo +1     
>         if i == 1: break
>     seznam.append(i)
>     return seznam
>
>
>
> ale tenhle algoritmus má tu nevýhodu, že bych ten seznam prvočísel (o velikost od 0 do sqrt(i)) musel vygenerovat, což trvá dost dlouho.
>
>   

Já bych si zkusil tipnout že toto bude ono s tím, že prostě mají v 
databázi prvních (sto) tisíc prvočísel na stálo, které se bud při startu 
serveru odněkud načtou nebo jednou vygenerují. Pokud to máš v obyčejné 
desktopové aplikaci, mohl by výpočet řady prvočísel běžet po startu v 
odděleném vláknu. A než se uživatel rozmyslí, co chce, bude hotovo.

-- 
geon
Pavel Kosina