Python - prvočísla: Porovnání verzí
mBez shrnutí editace |
Bez shrnutí editace |
||
Řádek 20: | Řádek 20: | ||
if integers[i]: | if integers[i]: | ||
print 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, 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) | |||
for i in range(len(prvocisla)): | |||
print prvocisla[i], # tisk bez odradkovani ukoncen carkou | |||
print | print |
Verze z 3. 12. 2005, 12:44
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, 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) for i in range(len(prvocisla)): print prvocisla[i], # tisk bez odradkovani ukoncen carkou print