A faire comme Eratosthène

Les derniers trucs auxquels vous avez joué, les derniers ordinateurs que vous avez bidouillés.

Modérateur : Politburo

Répondre
Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1549
Enregistré le : 21 août 2016 19:04

A faire comme Eratosthène

Message par Ben »

Le crible d'Eratosthène permet de trouver les nombres premiers entre 0 et N assez rapidement. Pour trouver les nombres premiers entre 0 et 1000, l’algorithme mets moins de 10 sec sur le C-128 en mode fast et moins de 20 sec sur le PB-700 pour les nombres entre 0 et 200.

Version C-128

Code : Tout sélectionner

5 fast:clr:ma=500
6 t=ti:m=int(sqr(ma*2))+1
7 dim ar$(ma)
10 for i=3 to m step 2
20 if ar$(i/2)="1" then 70
25 j=i*i/2
30 do while (j<ma+1)
40 ar$(j)="1"
50 j=j+i
60 loop
70 next i
75 for i=1 to ma
76 if ar$(i)<>"1" then n=n+1:print i*2+1;
77 next i
85 print "nbr de prems="; n
90 print "temps=";(ti-t)/60
99 end
Voici le premier jet de la version Pipe-line:

Code : Tout sélectionner

5 t=ti
10 dim a(2000)
20 a(1)=2:n=1:p=0
30 for i=3 to 10000 step 2
40 for j=1 to n
50 if i/a(j)=int(i/a(j)) then p=1:j=n
60 next j
70 if p=0 then n=n+1:a(n)=i:else p=0
90 next i
100 for i=1 to n:print a(i);:next i
110 print "temps=",(ti-t)/60
120 print "nbr=";n
Il y a encore pas mal de boulot d'optimisation :-)
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Eratosthène

Message par C.Ret »

Ah! BEN je n'avais pas vu ton message, je viens de poster par ailleurs une autre version de ce Crible E. pour nos C128 :

Code : Tout sélectionner

10 INPUT "Up to ";M% : TI$="000000" : R%=SQR(M%) : DIM P%(M%)
20 FOR N=2 TO M%  
30 :  IF P%(N)=0 THEN PRINT USING "#####";N; : IF N<=R% THEN FOR I=N*N TO M% STEP N : P%(I)=N : NEXT I
40 NEXT N : PRINT : PRINT TI$ : END
Avec cette version, facilement optimisable, j'obtiens les 1229 nombres premiers inférieurs à 10'000 en déjà seulement 2min15sec.
Jusqu'à 1000, il faut à peu près le même temps que ta version :

Code : Tout sélectionner

fast:run
Up to ? 1e3
    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  101  103  107  109  113  127  131
  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223
  227  229  233  239  241  251  257  263  269  271  277  281  283  293  307  311
  313  317  331  337  347  349  353  359  367  373  379  383  389  397  401  409
  419  421  431  433  439  443  449  457  461  463  467  479  487  491  499  503
  509  521  523  541  547  557  563  569  571  577  587  593  599  601  607  613
  617  619  631  641  643  647  653  659  661  673  677  683  691  701  709  719
  727  733  739  743  751  757  761  769  773  787  797  809  811  821  823  827
  829  839  853  857  859  863  877  881  883  887  907  911  919  929  937  941
  947  953  967  971  977  983  991  997
000012

ready.
Modifié en dernier par C.Ret le 07 avr. 2018 14:34, modifié 3 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: A faire comme Eratosthène

Message par gege »

Bonjour,
Il faudra forcément être prêt à tester la divisibilité jusqu'à racine(n) de toutes façons car le cas le plus défavorable existe (on peut facilement le construire).
G.E.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A faire comme Eratosthène

Message par C.Ret »

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.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Répondre

Retourner vers « A quoi t'as joué hier ? »