Nombre premier : algo

[SPH]

Bonjour,
Voici une routine qui m'a totalement scotché. Je sais bien que vous ne reconnaitrez pas le language mais ce n'est pas pour ca que vous ne comprendrez pas la logique. A propos de logique, pouvez vous m'expliquer comment fonctionne cette recherche extremement rapide de nombres premier ?

;
Define num.i = 10000
Define sqrnum.i = Sqr(num)+1
Dim PrimeFlags.b(num)
Dim Primes.i(num)
Define tim.i,count.i = 2
Define mill.i = ElapsedMilliseconds()
;
For x = 3 To sqrnum Step 2
      If PrimeFlags(x) = #False 
            tim = x + x
            Repeat
                  PrimeFlags(tim) = #True
                  tim + x
            Until tim >= num
      EndIf
Next 
;Local count:Int
Primes(1) = 2
For x = 3 To num Step 2
      If PrimeFlags(x) = #False 
            Primes(count) = x
            count+1   
            Debug x
      EndIf
Next
mill = ElapsedMilliseconds()-mill
;
MessageRequester("",StrF(mill/1000.0) +" seconds "+ Str(count)+" primes found!")

-----

[jiherve]

Bonsoir,
a vue de nez crible d’Ératosthène ou une variante.
JR

[SPH]

Moi j'avais pondu ca qui me semblait le top du top :

cmb=10000 ; combien de nombre premier on souhaite
Dim np(cmb); banque a nombre premier
nb.q=3 ; nb=3. c'est obligatoire.
np(1)=3; obligatoire aussi

temps=GetTickCount_() ; chronometre a zero

Repeat
i=1
racine=Sqr(nb)
;;;;;
While np(i)<=racine ; tant qu'on a pas testé jusqu'a la racine carré de NB
If nb%np(i)=0 ; on teste la division par les nombres premiers deja trouvé et mis en banque
Goto NP_suite ; on a trouvé un nombre non premier alors on va a la suite
EndIf
i+1
Wend
;;;;;
np(0)+1 ; on a trouvé un nombre premier alors on augmente np(0)
np(np(0))=nb ; et on ecris ce nombre premier en banque
;Debug nb
;;;;;
NP_suite:
nb+2 ; comme on ne teste que les nombres impairs, on saute de 2
Until np(0)=cmb ; on s'arretera quand on aura le compte de nombres premiers
np(0)=2 ; on ecris au debut de la banque le seul nombre premier pair


temps=GetTickCount_()-temps ; on stoppe le chronometre
MessageRequester("Erreur", Str(temps)+" ms")


For i=0 To cmb
  Debug np(i) ; on liste nos nombres premiers
Next

[invite0931ef5e]

je dirais que :
la première boucle "for" supprime(cad ne sont pas premiers) les multiples stricts d'abord de 3 puis de 5 puis 7 puis 11 etc en les mettant en true sauf 3,5,7,11 etc qui reste à false (les false sont les nombres premiers)
ensuite le "Step 2" dans la deuxième boucle élimine les multiples de 2, et le nombre premier 2 est donc pris à part avec Primes(1) = 2

[A voir en vidéo sur Futura]

[jiherve]

Re

je dirais que :
la première boucle "for" supprime(cad ne sont pas premiers) les multiples stricts d'abord de 3 puis de 5 puis 7 puis 11 etc en les mettant en true sauf 3,5,7,11 etc qui reste à false (les false sont les nombres premiers)
ensuite le "Step 2" dans la deuxième boucle élimine les multiples de 2, et le nombre premier 2 est donc pris à part avec Primes(1) = 2

Ce qui décrit donc un crible d'Erathostène, la plus vielle méthode connue.
JR