Python - prvočísla: Porovnání verzí

Z GeoWikiCZ
Skočit na navigaci Skočit na vyhledávání
m
Řá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, 13: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