Kribrilo de Eratosteno: Malsamoj inter versioj
| [nekontrolita versio] | [kontrolita revizio] |
Enhavo forigita Enhavo aldonita
Xqbot (diskuto | kontribuoj) e Bot: Replace deprecated <source> tag and "enclose" parameter; kosmetikaj ŝanĝoj |
de Eratosteno de Cireno |
||
| Linio 1: | Linio 1: | ||
La '''kribrilo de Eratosteno''' estas metodo por trovi serion da [[primo]]j komencante per 2. |
La '''kribrilo de Eratosteno''' estas metodo por [[Eratosteno de Cireno]] por trovi serion da [[primo]]j komencante per 2. |
||
[[Dosiero:New Animation Sieve of Eratosthenes.gif|dekstra|algoritmo montrita per animado]] |
[[Dosiero:New Animation Sieve of Eratosthenes.gif|dekstra|algoritmo montrita per animado]] |
||
Kiel registrite je 15:18, 31 jul. 2020
La kribrilo de Eratosteno estas metodo por Eratosteno de Cireno por trovi serion da primoj komencante per 2.
La algoritmo uzas tabelon de la naturaj nombroj (ĝis iu maksimumo) kaj forstrekas la ne-primojn kaj markas la primojn. Tiucele ĝi procedas laŭ jenaj paŝoj:
- Kreu tabelon de naturaj nombroj, komencante per 1, ĝis iu maksimuma nombro.
- Forstreku 1, kiu ne estas konsiderata primo.
- Serĉu la unuan (plej malgrandan) nombron, kiu estas nek markita nek forstrekita; marku ĝin kiel primon. Se ne restas tia nombro, la algoritmo finiĝas.
- Forstreku el la tabelo ĉiujn entjerajn oblojn de la ĵus trovita primo (do la 2-oblon, la 3-oblon, la 4-oblon ktp.).
- Reiru al paŝo 3.
Tiu algoritmo povas esti rikure skribita.
Jen ekzemplo en programlingvo Python :
def erat(l):
if not l or l[0]**2 > l[-1]:
return l
else:
return [l[0]] + erat([i for i in l if i%l[0]])
print (erat(range(2,1000)))
Jen ekzemplo en Common Lisp :
(defun erat (listo)
(if (or (null listo)
(> (expt (car listo) 2)
(car (last listo))))
listo
(cons (car listo)
(erat (loop for i in listo
unless (zerop (mod i (car listo)))
collect i)))))
(erat (loop for i from 2 to 1000 collect i))
