Kribrilo de Eratosteno: Malsamoj inter versioj
| [nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
e Bot: anstataŭigas evitindan ŝablonon per nova ŝablono |
Xqbot (diskuto | kontribuoj) e Bot: Replace deprecated <source> tag and "enclose" parameter; kosmetikaj ŝanĝoj |
||
| 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 trovi serion da [[primo]]j komencante per 2. |
||
[[ |
[[Dosiero:New Animation Sieve of Eratosthenes.gif|dekstra|algoritmo montrita per animado]] |
||
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: |
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. |
# Kreu tabelon de naturaj nombroj, komencante per 1, ĝis iu maksimuma nombro. |
||
| Linio 13: | Linio 13: | ||
Jen ekzemplo en [[programlingvo]] [[Python]] : |
Jen ekzemplo en [[programlingvo]] [[Python]] : |
||
< |
<syntaxhighlight lang='python'> |
||
def erat(l): |
def erat(l): |
||
if not l or l[0]**2 > l[-1]: |
if not l or l[0]**2 > l[-1]: |
||
| Linio 22: | Linio 22: | ||
print (erat(range(2,1000))) |
print (erat(range(2,1000))) |
||
</syntaxhighlight> |
|||
</source> |
|||
Jen ekzemplo en [[ |
Jen ekzemplo en [[Lisp (programlingvo)|Common Lisp]] : |
||
< |
<syntaxhighlight lang="common-lisp"> |
||
(defun erat (listo) |
(defun erat (listo) |
||
(if (or (null listo) |
(if (or (null listo) |
||
| Linio 37: | Linio 37: | ||
collect i))))) |
collect i))))) |
||
(erat (loop for i from 2 to 1000 collect i)) |
(erat (loop for i from 2 to 1000 collect i)) |
||
</syntaxhighlight> |
|||
</source> |
|||
{{Ĝermo|matematiko}} |
{{Ĝermo|matematiko}} |
||
Kiel registrite je 19:25, 18 apr. 2020
La kribrilo de Eratosteno estas metodo 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))
