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

Z GeoWikiCZ
mBez shrnutí editace
m (zpet)
 
(Není zobrazena jedna mezilehlá verze od stejného uživatele.)
Řádek 3: Řádek 3:
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.
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.


<source lang="python">
  #!/usr/bin/python
  #!/usr/bin/python
   
   
Řádek 22: Řádek 23:
   
   
  print
  print
</source>


'''Výpočet prvních ''N'' prvočísel'''
'''Výpočet prvních ''N'' prvočísel'''
Řádek 27: Řádek 29:
''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 ''
''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 ''


<source lang="python">
  #!/usr/bin/python
  #!/usr/bin/python
   
   
Řádek 55: Řádek 58:
   
   
  print
  print
</source>
[ [[Python|Zpět]] ]
{{Python}}

Aktuální verze z 20. 4. 2008, 19:41

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 ]