alors, si je comprend bien l'algo :
Code:
Define num.i = 15485864
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
Primes(count) = x
count+1
tim = x + x
Repeat
PrimeFlags(tim) = #True
tim + x
Until tim >= num
EndIf
Next
;Local count:Int
Primes(1) = 2
For y = x To num Step 2
If PrimeFlags(y) = #False
Primes(count) = y
count+1
EndIf
Next
mill = ElapsedMilliseconds()-mill
;
MessageRequester("",StrF(mill/1000.0) +" seconds "+ Str(count)+" primes found!")
Dans cette partie :
Code:
For x = 3 To sqrnum Step 2
If PrimeFlags(x) = #False
Primes(count) = x
count+1
tim = x + x
Repeat
PrimeFlags(tim) = #True
tim + x
Until tim >= num
EndIf
Next
L'algorithme met les flags de tout les multiples du nombre premier actuel dans le tableau PrimeFlags() à #True
Puis la fin du code met tout les nb premiers dans un tableau en regardant les flags.
En explication en français ça donne :
On initialise un tableau dont l'index des cases représente tout les nombres.
PrimeFlag(0), PrimeFlag(1), PrimeFlag(2), etc .... jusqu'à PrimeFlag(15485864)
il me semble qu'il y a 1 000 000 nb 1er avant 15485864.
Ensuite, on définit sqrnum qui est la racine du nombre maximum que nous regardons.
car sqrnum * sqrnum n'est forcément pas un nb 1er, et tous les multiples de (sqrnum + 1) sont déjà multiples de nb inférieurs à sqrnum, donc déjà tagés comme non premier.
l'algorithme part de 3 et progresse de 2 en 2, puisque tout les pairs ne sont pas premiers.
Donc, il prend le nombre 'x' actuel,
On regarde si x est tagé premier ou non, puis on marque tout les multiples de x (en faisant tim = x + x, puis tim = tim + x ) comme des nombres non premiers (dans l'algo c'est la valeur #true
attention c'est trompeur).
Puis on passe au nombre impair suivant, etc...
Comme tout les multiples de chaque nombre premiers est marqué comme non premier, bah il suffit de relevé tout les tag #false du tableau, et on a la liste des nombres premiers.
Ce qui est bien, c'est que chaque nombre n'est traité qu'une seule fois, entrainant ainsi un gain de temps énorme
Voili voilou, j'espère que c'est clair maintenant
FAQ
Rechercher
M’enregistrer
Connexion
