Python - prvočísla

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
       r = p % n
 
       if r == 0:                 # p neni prvocislo, zkousim p+2
          p = p + 2
          k = 1
          break
 
       if p <= n*n:               # p je prvocislo
          break; 
 
    prvocisla.append(p)           # pridam dalsi prvocislo do seznamu
 
 
 for i in range(len(prvocisla)):
    print prvocisla[i],           # tisk bez odradkovani ukoncen carkou
 
 print

[ Zpět ]