Page 1 sur 1
[R] Définir array
Posté : lun. 15 sept. 2008 19:47
par Varal7
Bonjour, je souhaite créer un script qui me permette de faire la liste des premiers nombres premiers
Voici :
Code : Tout sélectionner
dim $premier[0] = 2
$nombre_de_nombre_premier = 0
for $nombre = 3, to 100
for $i = 0, to $nombre_de_nombre_premier
if $i = $nombre_de_nombre_premier Then
if $nombre/$premier[$i] = int($nombre/$premier[$i]) Then
ExitLoop
Else
$premier[$nombre_de_nombre_premier+1] = $nombre
$nombre_de_nombre_premier = $nombre_de_nombre_premier+1
EndIf
if $nombre/$premier[$i] = int($nombre/$premier[$i]) Then
ExitLoop
EndIf
EndIf
Next
Next
For $count = 0 to $nombre_de_nombre_premier
MsgBox(0,"Nombre permier #"&$count, $premier[$count])
Next
Le débugguer me dit : Array variable subscript badly formatted.
Comment définir un Array sans donner la valeur à chaque varaiable ?
Merci d'avance
Re: [R]Définir array
Posté : lun. 15 sept. 2008 21:46
par sylvanie
Le plus simple à mon goût, après c'est une histoire de préférence, c'est de passer par une chaîne de caractère que l'on retransforme grâce à stringsplit, exple "2|3|5 ...."
cijoint l'algo avec cette méthode + une petite optimisation :
Code : Tout sélectionner
$premier = "2"
$nombre_de_nombre_premier = 0
for $nombre = 3 to 100
$tab_premier=StringSplit($premier,"|")
$nombre_de_nombre_premier=$tab_premier[0]
$is_prime_number=1
$limite_to_search=Sqrt($nombre)
for $i = 1 to $nombre_de_nombre_premier
$division=$nombre/$tab_premier[$i]
if $division = int($division) Then
; not prime number
$is_prime_number=0
ExitLoop
Else
If ($limite_to_search>$division) Then
;the search may be interrupted due to the fact that if another greater
;prime number devides $nombre then the second coefficient will be smaller than $tab_premier[$i]
; ie this one would have to devide it before to reach this value ...
ExitLoop
EndIf
EndIf
Next
if ($is_prime_number=1) Then
;prime number detected
$premier&="|"&$nombre
EndIf
Next
$final_msg=""
For $count = 1 to $nombre_de_nombre_premier
$final_msg&="Nombre permier #"&$count&" : "&$tab_premier[$count]&@CRLF
Next
MsgBox(0,"List of prime numbers up to 100", $final_msg)
Re: [R] Définir array
Posté : lun. 15 sept. 2008 23:20
par sylvanie
Allez, pour la route, un petit concours, entre la dernière méthode classique vue précédement et le test de Rabin-Miller (cf
http://teal.gmu.edu/crypto/student_proj ... sld006.htm par exple) :
► Afficher le texte
Code : Tout sélectionner
$timer1=TimerInit()
$premier = "2"
$nombre_de_nombre_premier = 0
for $nombre = 3 to 10000
$tab_premier=StringSplit($premier,"|")
$nombre_de_nombre_premier=$tab_premier[0]
$is_prime_number=1
$limite_to_search=Sqrt($nombre)
for $i = 1 to $nombre_de_nombre_premier
$division=$nombre/$tab_premier[$i]
if $division = int($division) Then
; not prime number
$is_prime_number=0
ExitLoop
Else
If ($limite_to_search>$division) Then
;the search may be interrupted due to the fact that if another greater
;prime number devides $nombre then the second coefficient will be smaller than $tab_premier[$i]
; ie this one would have to devide it before to reach this value ...
ExitLoop
EndIf
EndIf
Next
if ($is_prime_number=1) Then
;prime number detected
$premier&="|"&$nombre
EndIf
Next
$final_msg=""
For $count = 1 to $nombre_de_nombre_premier
$final_msg&="Nombre permier #"&$count&" : "&$tab_premier[$count]&@CRLF
Next
FileWrite("nbr_prem1.txt",$final_msg)
;MsgBox(0,"List of prime numbers up to 100", $final_msg)
ConsoleWrite("tps : "&TimerDiff($timer1)&@CRLF)
; méthode Rabin Miller
$timer2=TimerInit()
$premier = "2"
$nombre_de_nombre_premier = 0
for $nombre = 3 to 10000
;ConsoleWrite($nombre&@CRLF)
If (Rabin_Miller($nombre,5)) Then $premier&="|"&$nombre
Next
$tab_premier=StringSplit($premier,"|")
$nombre_de_nombre_premier=$tab_premier[0]
$final_msg=""
For $count = 1 to $nombre_de_nombre_premier
$final_msg&="Nombre permier #"&$count&" : "&$tab_premier[$count]&@CRLF
Next
FileWrite("nbr_prem2.txt",$final_msg)
;MsgBox(0,"List of prime numbers up to 100", $final_msg)
ConsoleWrite("tps : "&TimerDiff($timer2)&@CRLF)
; the number of test grant that we have a probability of 1-(1/4)^number of test that the number is prime
;ie 5 tests => 99,90234375 %
Func Rabin_Miller($nb_to_test,$number_of_test)
;function [y]=rabin_miller(p,nb)
Local $nb_minus,$power=0,$div,$ind,$conditon,$a,$j,$z
if $nb_to_test=2 Or $nb_to_test=1 Or $nb_to_test=3 then
return 1
EndIf
if BitAND($nb_to_test,1)=0 then ; or if mod($nb_to_test,2)==0
;2 devides $nb_to_test
return 0;
EndIf
$nb_minus=$nb_to_test-1;
$power=1;
$div=BitShift($nb_minus,1) ; or $div=$nb_minus/2
while (BitAND($div,1)=0)
$power+=1
$div=BitShift($div,1)
Wend
; ConsoleWrite("div "&$div&@CRLF)
; ConsoleWrite("power "&$power&@CRLF)
For $ind=1 To $number_of_test
$conditon=1
$a=Random(2,$nb_minus,1)
; ConsoleWrite("a "&$a&@CRLF)
$j=0
$z=speed_exp($a,$div,$nb_to_test);Mod($a^$div,$nb_to_test)
; ConsoleWrite("z = "&$z&@CRLF)
if (($z=1) Or ($z=$nb_minus)) then
ContinueLoop
EndIf
while ($conditon=1)
if ($j>0) And ($z=1) then
Return 0
EndIf
$j+=1;
; ConsoleWrite("j interne = "&$j&@CRLF)
; ConsoleWrite("z interne = "&$z&@CRLF)
if ($j<$power) And ($z<>$nb_minus) then
$z=speed_exp($z,2,$nb_to_test);Mod($z^2,$nb_to_test)
else
$conditon=0;
EndIf
Wend
if ($z==$nb_minus) then
ContinueLoop;
EndIf
if ($j=$power) And ($z<>$nb_minus) then
Return 0
EndIf
Next
Return 1
EndFunc
Func speed_exp($a,$x,$n)
Local $tmp
if $x=1 then Return mod($a,$n)
if BitAND($x,1)==0 then
$tmp=speed_exp($a,BitShift($x,1),$n)
$tmp=Mod($tmp^2,$n);
return $tmp
else
$tmp=speed_exp($a,BitShift($x-1,1),$n);
$tmp=mod($tmp^2,$n);
$tmp=mod($tmp*$a,$n);
return $tmp;
EndIf
EndFunc
Sur mon vieux PC :
75 secondes pour la méthode 1 et 10000 nombres à analyser
25 secondes pour Rabin-Miller
Re: [R] Définir array
Posté : sam. 20 sept. 2008 14:10
par Varal7
Merci beaucoup beaucoup.
Désolé de ne répondre que maintenant, mais j'ai été pris par le temps.
Code : Tout sélectionner
HotKeySet("{ESC}", "Terminate")
$premiers = "2"
$nombre_de_nombre_premier = 0
MsgBox(0, "ATTENTION", "A été testé sur windows XP et Vista")
MsgBox(0, "Important", "Si le porgramme a déjà été utilisé, merci de supprimer le fichier nbr_ prem1.txt")
$fin = inputBox("Premiers nombres premiers", "Jusqu à quel nombre voulez-vous effectuer le test ?"&@CRLF&">10 000 déconseillé",100)
MsgBox(0,"Arrêter le programme","À tout moment vous pouvez arrêter le programme par la touche Echap")
progressOn("Recherche en cours","Nombres testés :","0")
for $nombre = 3 to $fin ;$nombre est le nombre qu'on teste
progressSet($nombre/$fin*100,$nombre&" sur "&$fin)
$premier_array=StringSplit($premiers,"|") ;$premiers = 2|3|5|7|11|... et on en fait un array $premier_array :
;$premier_array[1] = 2 ; $premier_array[2] = 3 ; etc.
;et $premier_array[0] est égal au nombre de valeurs.
$nombre_de_nombre_premier=$premier_array[0]
$est_premier=true ;on dit que $nombre est premier.
$limite_du_test =Sqrt($nombre)
for $i = 1 to $nombre_de_nombre_premier
$quotient=$nombre/$premier_array[$i]
if $quotient = int($quotient) Then ;si l'approximation décimale est égale à la partie entière de l'approxiamtion
$est_premier=false ;alors $nombre n'est pas premier
ExitLoop ; et on peut alors sortir de la boucle et passer à $nombre =$nombre+1
Else
If ($limite_du_test>$quotient) Then
;On atteint la racinne carrée et il devient inutile de continuer
ExitLoop
EndIf
EndIf
Next
if ($est_premier=true) Then ; si le nombre est premier, on le rajoute à la liste
$premiers= $premiers&"|"&$nombre
EndIf
Next
ProgressOff()
ProgressOn("Ecriture des nombres premiers", "Nombres écrits :")
$final_msg=""
For $count = 1 to $nombre_de_nombre_premier
progressset($count/$nombre_de_nombre_premier*100,$count&" sur "&$nombre_de_nombre_premier)
$final_msg&="Nombre premier #"&$count&" : "&$premier_array[$count]&@CRLF
Next
progressoff()
FileWrite("nbr_prem1.txt",$final_msg);on stocke les nombres premiers dans le fichier "nbr_prem1.txt"
MSgBox(0,"Recherche terminée","Les nombres premiers sont stockés dans le fichier nbr_prem1.txt")
call("Terminate")
Func Terminate()
MsgBox(0,"About", "http://www.autoitscript.fr/forum/viewtopic.php?f=3&t=1558")
Exit 0
EndFunc
Voici le code que j'en ai tiré, assorti de commentaire...