Liste les nombres premiers

Soyez le premier à donner votre avis sur cette source.

Vue 4 662 fois - Téléchargée 261 fois

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

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_Julien39
Messages postés
6413
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
17 mai 2018
250 -
L'application la plus connue est sans doute la cryptographie, je sais pas si quelqu'un a déja entendu parler du systeme RSA qui est utiisé pour les sites sécurisés et chiffrer les mail dont l'algorithme est basé sur les nombres premiers. Mais un site l'explique mieux que moi http://sebsauvage.net/comprendre/encryptage/crypto_rsa.html

Sinon il y a des trucs bien simpa à faire qui ne servent pas forcément a quelque chose de concret mais c'est assez interessant de travailler sur les nombres premiers. J'ai plusieurs exemples mais je ne sais pas si sa t'interresse.
zemetafyzik
Messages postés
119
Date d'inscription
jeudi 17 juin 2004
Statut
Membre
Dernière intervention
3 novembre 2007
1 -
par exemple sa sert pour coder les messages (les clef de codage...)
ScSami
Messages postés
1488
Date d'inscription
mercredi 5 février 2003
Statut
Membre
Dernière intervention
3 décembre 2007
18 -
Dite, moi je suis bien gros et pourtant, tellement petit que j'ai une question à la con n'étant pas fort en maths :
A quoi ça sert les nombres premiers ???
Qu'est-ce qu'on peut faire avec ???
zemetafyzik
Messages postés
119
Date d'inscription
jeudi 17 juin 2004
Statut
Membre
Dernière intervention
3 novembre 2007
1 -
euh...puis - je encore poster ???
en fait, meme le 'step' marche pas dans le code, j'arrive pas a comprendre finalement :'(


il y a des moments comme cela ou l'on aimerai ce faire tout petit petit
zemetafyzik
Messages postés
119
Date d'inscription
jeudi 17 juin 2004
Statut
Membre
Dernière intervention
3 novembre 2007
1 -
ouuups :D
If (n And 1) = 0 Then
Exit For
'Si n pair on sort de la boucle
End If

désolé, j'ai voulu faire le malin. (mais pour me ratrapper jvai quand meme dire sa : tu fais un test pou rien :) (si tu met le "step" :) )

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.