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
_______________________________________________
Python mailing list
[email protected]
http://www.py.cz/mailman/listinfo/python
