procedure UDivMod(const Dividend, Divisor: LongWord; var Result, Remainder: LongWord); register;
asm
push ebx;
mov ebx,edx;
xor edx,edx;
div ebx;
mov ebx,Remainder;
mov [ecx],eax;
mov [ebx],edx;
pop ebx;
end;
function IsPrimeNumber(const Number: LongWord): boolean;
var DivisorA,
DivisorB,
Modulo,
DivisorsCount : LongWord;
begin
Result := false;
if Number < 2 then
exit;
DivisorA := 1;
DivisorB := Number;
Modulo := 0;
DivisorsCount := 0;
if DivisorA < DivisorB then
repeat
UDivMod(Number, DivisorA, DivisorB, Modulo);
if Modulo = 0 then
DivisorsCount := DivisorsCount + 2;
DivisorA := DivisorA + 1;
until (DivisorA >= DivisorB) or (DivisorsCount >= 3);
Result := DivisorsCount = 2;
end;
Remarque :
~4,5 millions de cycles / 1.3 secondes (boucle comprise) pour trouver les 100 000 nombres premier en partant de 1 (soit 1 299 710 nombres testés).
~8 millions de cycles / 2.25 secondes (boucle comprise) pour trouver les 100 000 nombres premier suivant,donc en partant de 1 299 710, soit 1 450 450 nombres testés.
~48.6 millions de cycles / 13.5 secondes (boucle comprise) pour trouver les 500 000 nombres premiers en partant de 1, soit 7 368 788 nombres testés.
Function isNP(ByVal Nb As Long) As Boolean
' TEST SI NB EST UN NOMBRE PREMIER ( ALGO RAPIDE )
' utilise ERATHOSENE et DIVISIONS
' Test de validit‚
If Nb < 2 Then Exit Function
' ParamŠres
Dim Liste As Integer
Dim Saut As Integer
Dim t As Integer
Dim A As Long
Dim A1 As Integer
Dim A2 As Integer
Dim Pi_NbP As Integer
Dim Pi_Nbp2 As Integer
Dim Prod As Long
Dim nbp2 As Integer
Dim t2 As Integer
Dim fin As Long
Dim m As Long
' ParamŠtres d'optimisation
Pi_NbP = 5 'indice de 0 … 5
Prod = 30030 'produit de 2*3*5*7*11*13
' ALGO ERATHOSTENE : G‚n‚re liste nb premier jusqu'… pi(A+1)
A = Prod + 1
A1 = CInt(Int((A ^ 0.5 - 3) / 2))
A2 = CInt((A - 3) / 2)
Dim Nbp(A2) As Boolean
For Liste = 0 To A1
If Nbp(Liste) = False Then
Saut = 2 * Liste + 3
For t = CInt((Saut ^ 2 - 3) / 2) To A2 Step Saut
Nbp(t) = True 'pas premier
Next t
End If
Next Liste
' Forme la liste
Dim L(A2 + 1) As Long
L(0) = 2
Pi_Nbp2 = 0
For t = 0 To A2
If Nbp(t) = False Then
Pi_Nbp2 = Pi_Nbp2 + 1
L(Pi_Nbp2) = 2 * t + 3
End If
Next t
' Test si trivial
If Nb > Prod Then GoTo suite '‚vite si pas n‚cessaire
For t = 0 To Pi_Nbp2
If Nb = L(t) Then isNP = True : Exit Function
Next t
suite:
' Test si multiple
For t = 0 To Pi_Nbp2
If Nb = L(t) * Int(Nb / L(t)) Then Exit Function
Next t
' Forme liste complŠte
Dim L2(5627) As Long
For t = Pi_NbP + 1 To Pi_Nbp2
nbp2 = nbp2 + 1
L2(nbp2) = L(t)
Next t
' On rajoute les multiples
For t = Pi_NbP + 1 To Pi_Nbp2
If L(t) * L(t) > A Then Exit For
For t2 = t To Pi_Nbp2
If L(t) * L(t2) < A Then
nbp2 = nbp2 + 1
L2(nbp2) = L(t) * L(t2)
Else
Exit For
End If
Next t2
Next t
' ALGO DIVISIONS
fin = CLng(Math.Sqrt(Nb))
For m = 0 To fin Step Prod
For t = 1 To nbp2
If Nb = (m + L2(t)) * Int(Nb / (m + L2(t))) Then Exit Function
Next t
Next m
isNP = True
End Function
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
'Chrono
Dim Stopwatch As System.Diagnostics.Stopwatch
Stopwatch = New Stopwatch
'Donn‚e
Dim a As Long
a = CLng(TextBox1.Text)
Dim b As Boolean
Stopwatch.Start()
b = isNP(a)
Stopwatch.Stop()
'Renvoi
MsgBox(b & " " & Stopwatch.Elapsed().TotalMilliseconds & " millisecondes")
End Sub
Remarque :
Mettre :
- La fonction dans un module
- Une Form1 composée de 1 TextBox + 1 Bouton (+ le code)
On peut tester la borne "999999999989" qui renvoit vrai en environ 15 millisecondes sur processeur 2 GHz.
proc IsPrime {n} {
set max [expr {int(sqrt($n))}]
incr max
set res 1
for {set i 3} {$i < $max} {incr i 2} {
if {!($n % $i)} {
set res 0
break
}
}
return $res
}