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
