Liste les nombres premiers

Télécharger le projet
Commenter

Description

Ce programme liste les nombres premiers. Ceux ci sont trouvés grace à l'utilisation de deux boucles. C'est un code tres simple dont la vitesse est améliorée à l'aide de quelques techniques propres aux nombres premiers. Ces techniques sont expliqués et démontrés en commentaire dans le code.

Source / Exemple : 


Function Premier(n As Long) As Boolean

Premier = True

If n = 1 Or n = 0 Then
   Premier = False
   Exit Function
End If

If n = 2 Or n = 3 Or n = 5 Or n = 7 Or n = 11 Or n = 13 Then
   Exit Function
End If

'Traitement des cas particuliers

For i = 1 To ((Sqr(n)) / 6) + 1

   'Si n est un entier composé (non premier) appelons p le plus petit diviseur différent de 1 de n.
   'Supposons que p n'est pas premier alors il existe un unique k différent de 1 qui divise p
   'donc n=p*p' (p étant un entier naturel)
   '      =k*k'*p'
   'donc k est un diviseur de n et k>1 et k<p
   'd'où une contradiction car le plus petit diviseur de n est p donc p est premier et p>=2
   'n=p*p'
   'et p<p' car p' diviseur de n donc supérieur à p qui est le plus petit
   'donc p*p<p*p'
   ' et donc p<sqr(n)
   'donc si n est un entier composé il existe un diviseur premier de n tel que 2<p<sqr(n)
   'par conséquent si p est premier il n'en existe pas donc on peut s'arreter de vérifier à partir de sqr(n)
   
   DoEvents

   
   If (n And 1) = 0 Then
      Premier = False
      Exit Function
      'Si n pair on sort de la boucle
   End If

   
   If n Mod 3 = 0 Then
      Premier = False
      Exit For
      'Si n divisible par 3 on sort de la boucle
   End If

   
   If n Mod (6 * i - 1) = 0 Then
      Premier = False
      Exit For
   End If

   
   If n Mod (6 * i + 1) = 0 Then
      Premier = False
      Exit For
      '6i-1 et 6i+1 exclu les nombres pair ainsi que les multiples de 3 car si on arrive à cette étape on sait que n n'est divisible ni par 3 ni par 2 donc par conséquent n ne sera pas divisible par 4,6,8,9...
      'si le reste de la division euclidienne de n/(6i+-1) = 0 cad n est divisible par 6i+-1 et 2<(6i+-1)<n donc n n'est pas premier
   End If

Next i

End Function
Télécharger le projet

Codes Sources

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 (cs_Julien39)