Dne 12. prosinec 2008 16:34 Jakub Vojáček <[email protected]> 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 _______________________________________________ Python mailing list [email protected] http://www.py.cz/mailman/listinfo/python
