A la recherche des (petits) nombres premiers

Bonjour, je vous propose un d=E9fi (si vous me permettez)

Comme je m'int=E9resse =E0 la cryptographie (dans un but purement
lucratif puisque je travail dans l'=E9dition de soft qui tournent autour
de la s=E9curit=E9) je suis tomb=E9 sur un ouvrage qui d=E9crit le "Tamis
d'Eratosthenes". C'est une tr=E8s mauvaise id=E9e de lire des ouvrages de
ce types le soir : =E7a emp=EAche de dormir. Toujours est-il que le
lendemain matin j'ai pondu un algo (qui =E0 certainement =E9t=E9 trouv=E9
par quelque milliers de personnes avant moi, suite aux m=EAmes
insomnies). Voici l'id=E9e =E9trange qui m'est venue : pourquoi ne pas
compter dans une base tordue qui permettrait de faire appara=EEtrait les
nombres premiers.

5 3 2
2 -> | | | 1 |
3 -> | | 1 | 0 |
4 -> | | 0 | 2 |
5 -> | 1 | 0 | 0 |
6 -> | | 1 | 1 |
7 -> | | | 0 |
8 -> | | | 1 |
.=2E..

D'accord l'id=E9e n'est pas originale, au point que l'on appelle cette
op=E9ration en "d=E9composition en facteur premier" (dignes souvenirs de
la classe de troisi=E8me). On voit que les multiples de 2 apparaissent
une fois sur deux, les 3 apparaissent... et un nouveau nombre premier
appara=EEt quand =E0 sa droite il n'y a que des 0.
Mon algo tient =E9videment dans la derni=E8re phrase. Reste =E0
initialiser deux compteurs, d=E9compter et lorsque l'on arrive =E0 0 le
r=E9initialiser =E0 sa valeur d'origine. Et si tous les compteurs
arrivent =E0 0 en m=EAme temps on a trouv=E9 un nouveau nombre premier :
on cr=E9e un nouveau compteur.

Donc voici le "d=E9fi" :
Cet algo porte-t-il un nom ? Et a quel point n'est il pas meilleur que
celui de notre ami Eratosthenes ? C'est d'ailleurs l=E0 que je vais vous
laisser chercher pour comparer les performances en termes de ressources
et de temps de calcul ( car je n'ai pas le temps de faire ce petit
exercice sur mon temps libre, je suis papa depuis quelques semaines et
je ne touche plus mon PC =E0 la maison).

Pour terminer voici l'algo cod=E9 en Lisp (ou plus pr=E9cis=E9ment en
elisp pour ceux qui utilisent emacs ou xemacs, pour les autres je peux
transcrire en C)

;(setq primes (list (cons 1 2) (cons 2 3)))
;(setq iterator primes)
;(setq counter 1)

(progn (let ((primes (list (cons 1 2)))
(counter 3))
;(while (> 10 (cdr (nth 0 primes)))
(while (> 100000 counter)
(let ((iterator primes)
(newprime t))
(while (not (null iterator))
(if (zerop (caar iterator))
(progn (setq newprime nil)
(setcar (car iterator) (1- (cdar iterator))))
(setcar (car iterator) (1- (caar iterator))))
(setq iterator (cdr iterator)))
(if newprime (nconc primes (list (cons (1- counter)
counter))))
(incf counter)
(setq iterator primes)
(setq newprim t)))
(setq iterator primes)
(while (not (null iterator))
(insert (format "%s " (cdar iterator)))
(setq iterator (cdr iterator)))))