0

Nombres premiers

La crible d’ératosthène permet de trouver les n premiers nombres premiers en parcourant de 2 à n tous les nombres et en supprimant les multiples

Lire la suite de l’article pour voir L’algorithme et l’implémentation en Visual Basic

Déscription et implementation visuel (source Wikipedia) :

L’algorithme procède par élimination : il s’agit de supprimer d’une table des entiers de 2 à N tous les multiples d’un entier. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d’aucun entier, et qui sont donc les nombres premiers..

On commence par rayer les multiples de 2, puis à chaque fois on raye les multiples du plus petit entier restant.

On peut s’arrêter lorsque le carré du plus petit entier restant est supérieur au plus grand entier restant, car dans ce cas, tous les non-premiers ont déjà été rayés précédemment.

À la fin du processus, tous les entiers qui n’ont pas été rayés sont les nombres premiers inférieurs à N.

http://fr.wikipedia.org/wiki/Crible_d’%C3%89ratosth%C3%A8ne

Algorithmes Nombres Premiers Crible d’Ératosthène

ENTIER NbrMax
ENTIER i

REEL  NbrPrem
NbrPrem <--2

AFFICHER "entrer un entier"
LIRE NbrMax

TABLEAU booleen TabNbr(NbrMax)

TANTQUE NbrPrem * nbrPrem < NbrMax  FAIRE

   i <-- 2 * NbrPrem

   FAIRE 
      TabNbr(i)=vrai
      i <-- i + NbrPrem
   JUSQUA i > NbrMax

   FAIRE 
      NbrPrem <-- NbrPrem + 1
   JUSQUA TabNbr(NbrPrem)=Faux 

FTQ

POUR i ALLANT DE 2 A NbrMax
   SI TabNbr(NbrPrem)=Faux ALORS
      AFFICHER tabNbr(i)
   FSI
FIN POUR

[Visual Basic] Algorithme Nombre Premier Crible d’Ératosthène

'on recupere le nombre à traiter
Dim NbrMax As Integer
NbrMax = CInt(T_nbr.Text)
'le tableau des nombres premiere
Dim tabnbr() As Boolean
ReDim tabnbr(NbrMax)
'les nombres premier
Dim NbrPrem As Long
NbrPrem = 2 'le premier est 2
Dim i As Integer

'met le tableau et la zone de liste a vide
For i = 0 To UBound(tabnbr) - 1
    tabnbr(i) = False
Next i
lst_premier.Clear

'tant que NbrPrem est inférieur à la racine carré du nombre donnée (NbrMax)
'nous allons l'incrementer
Do While NbrPrem * NbrPrem < NbrMax
    'on defini le premier multiple de NbrPrem
    i = 2 * NbrPrem
    'puis on met a vrai tout les multiple de NbrPrem
    'jusqu'a ce que l'on atteingne le nombre donnée (NbrMax)
     Do
     	tabnbr(i) = True
        i = i + NbrPrem
     Loop Until i > NbrMax

    'On passe on nombre premier suivant, soit le prochain que l'on trouve à  false
     Do
     	NbrPrem = NbrPrem + 1
     Loop Until tabnbr(NbrPrem) = False
Loop

'Affichage des nombres premier dans la zone de liste
For i = 2 To NbrMax
  If tabnbr(i) = False Then
     lst_premier.AddItem i
  End If
Next i

End Sub

You must be logged in to post a comment.