Test Nombre Premier

Commenter

Contenu du snippet 

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

Compatibilité : VB 2008

Disponible dans d'autres langages :

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (us_30)