Kribrilo de Eratosteno

La kribrilo de Eratosteno estas metodo por trovi serion de primoj komencante per 2, supozeble elpensita far Eratosteno de Kireno.

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:

1. Kreu tabelon de naturaj nombroj, komencante per 1, ĝis iu maksimuma nombro.
2. Forstreku 1, kiu ne estas konsiderata primo.
3. 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.
4. Forstreku el la tabelo ĉiujn entjerajn oblojn de la ĵus trovita primo (do la 2-oblon, la 3-oblon, la 4-oblon ktp.).
5. 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))