Python - prvočísla: Porovnání verzí
mBez shrnutí editace |
mBez shrnutí editace |
||
Řádek 49: | Řádek 49: | ||
break; | break; | ||
prvocisla.append(p) | prvocisla.append(p) # pridam dalsi prvocislo do seznamu | ||
Verze z 3. 12. 2005, 13:07
Eratosthenovo síto.
Vytvoříme seznam přirozených čísel menších než N. První prvočíslo je 2, označíme tedy v našem sezmanu všechny násobky čísla 2 (která z definice nemohou být prvočísly). Přejdeme na další neoznačené číslo v seznamu, tj. na číslo 3 a celý proces opakujeme, dokud není zpracován celý seznam.
#!/usr/bin/python N = 100 integers = [1]*N for i in range(2, N): if integers[i]: k = 2 n = i*k while n < N: integers[n] = 0 k = k + 1 n = i*k for i in range(1, N): if integers[i]: print i, print
Výpočet prvních N prvočísel
Donald E. Knuth: The Art of Computer Programming, Vol 1, Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997, ISBN 0-201-89683-4, str. 147-149
#!/usr/bin/python prvocisla = [1, 2, 3] # ulozim prvni tri prvocisla N = 100; while len(prvocisla) < N: p = prvocisla[-1] + 2 # [-1]: konec neprazdneho seznamu k = 1 # test: zacinam prvocislem 2 while k<len(prvocisla): n = prvocisla[k] # n je k-te nalezene prvocislo k = k + 1 q = p / n r = p % n if r == 0: # p neni prvocislo, zkousim p+2 p = p + 2 k = 1 break if q <= n: # p je prvocislo! (viz Knuth) break; prvocisla.append(p) # pridam dalsi prvocislo do seznamu for i in range(len(prvocisla)): print prvocisla[i], # tisk bez odradkovani ukoncen carkou print