Oui, utiliser les tests de divisibilités est une alternative.
mais ici, il n'y a pas de test utilisant une quelconque division. Le principe du crible revient à construire le tableau P%() qui pour tout élément de l'intervalle parcouru, contient soit 0 pour indiquer un nombre premier, soit un des multiples pour les nombres composés.
Ainsi, rechercher les nombres premiers entre 2 et 100 donne la liste suivante assez rapidement (pour un CBM 8 bit 2 Mhz) :
Code : Tout sélectionner
run
Up to ? 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
59 61 67 71 73 79 83 89 97
00h00'02"
ready.
Mais laisse en mémoire le Crible d'Eratosthène suivant ( j'ai ajouté les nombres premiers i: pour mieux voir le truc à chaque p%(i) nul :
Code : Tout sélectionner
for i=1 to m%:? using u$;p%(i);:next i
1:0 2:0 3:0 2 5:0 2 7:0 2 3 2
11:0 3 13:0 2 3 2 17:0 3 19:0 2
3 2 23:0 3 5 2 3 2 29:0 5
31:0 2 3 2 5 3 37:0 2 3 5
41:0 3 43:0 2 5 2 47:0 3 7 5
3 2 53:0 3 5 7 3 2 59:0 5
61:0 2 7 2 5 3 67:0 2 3 7
71:0 3 73:0 2 5 2 7 3 79:0 5
3 2 83:0 7 5 2 3 2 89:0 5
7 2 3 2 5 3 97:0 7 3 5
ready.
Ah! Oui, zut, 1 n'est plus premier aujourd'hui ! Il l'était il y a encore peu de temps.
On observera cependant que ta remarque concernant le test limité à la racine carrée de (n) est pertinente, en effet, il n'y pas dans ce crible de multiple supérieur à 7.
Et pour cause, la racine carrée de 100 étant 10; les seuls facteurs preùier multiples envisageables sont 2 3 5 et 7
Tel qu'il est construit, l'algorithme se limite donc naturellement et sans effort à cette fameuse racine.
Et oui.