[python] Faktorizace

[Jan Bednařík]

Dne 12. prosinec 2008 16:34 Jakub Vojáček <Jakohv na seznam.cz> napsal(a):
> 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

Není to náhodou tím, že ta stránka dělá něco úplně jiného - nerozkládá
na součin prvočísel, ale jen zjišťuje, jestli je číslo prvočíslo? :-)

> 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.

Naštěstí seznamy prvočísel vygenerovala spousta lidí před tebou, stačí
je jen k tvému programu přiložit. Např. http://primes.utm.edu

Pokud ale budeš chtít k programu přiložit víc než prvních pár miliónů
prvočísel, doporučuju uložit si jejich databázi metodou popsanou zde
http://www.rsok.com/~jrm/printprimes.html

Honza