Nombres premiers

Dernière mise à jour le par pijaku .

Nombres premiers

Une première propriété qui est la base de tout.

Un entier naturel est dit premier s'il admet 2 diviseurs distincts.

Définition

Si n n'est pas premier alors on dit que n est composé. C'est logique car s'il n'est pas premier il existe un d et k appartenant à N tels que n=dk, n est composé de d et k

Ensemble fini ou infini ?

Nous pouvons maintenant nous demander si cet ensemble est fini ou infini ?
Supposons que l'ensemble des nombres premiers est fini. Soit q le plus grand de ces nombres premiers et J = q! + 1
Supposons que J est composé, il existe alors p appartenant à N tel que p divise J et p >1
Comme q est le plus grand des nombres premiers 2Or 1 = J - q! et on sait que p divise J et
p divise q! donc p divise 1 donc p=1
Ce qui est impossible car p<1 d'où une contradiction donc J est premier.
De plus J>q donc q n'est pas le plus grand nombre premier. D'où une contradiction
Donc l'ensemble des nombres premiers est infini.

Raisonnement

En partant de ces dernières choses nous allons construire un raisonnement qui nous sera utile pour optimiser les programmes sur les nombres premiers.
Soit n un entier composé, appelons p le plus petit diviseur de n différent de 1.
Supposons que p n'est pas premier alors il existe k différent de 1 qui divise p or n=p*p' donc n=k*k'*p'
Donc k est un diviseur de n et k>1 et k et p²<N
Conclusion : Si n est un entier composé alors il admet au moins un diviseur premier compris entre 1 et sqr(n)

Utilité : pour savoir si un nombre est premier on doit chercher s'il est divisible s'il n'existe aucun diviseur de ce nombre entre 1 et la racine du nombre alors il n'en existe pas dans N et le nombre est premier.

Code

'Pour un programme qui teste le nombre a

For i=2 to sqr(a)+1
    If a/i=int(a/i) Then
        Premier = false
        exit for
    End if
Next i
                                                            
If i> sqr(a) Then
    Premier = true
    Exit for
End if

Dans un but d'optimisation des programmes nous remarquons que certains types de nombres ne sont jamais premiers, il est donc inutile de les vérifier dans une recherche.
Les nombres pairs : un nombre pair est un nombre qui admet 2 comme diviseur et donc n'est pas premier (sauf 2).
Soit (un) la suite des nombres pairs un= 2n. Nous savons que lorsque n>1 un n'est pas premier quelque soit n. Les nombres de la forme 2n+1 sont peut être premiers.
Nous pouvons traiter de la sorte les multiples de chaque nombres les multiples de 3 sont a exclure pour les mêmes raisons un = 3n, un n'est pas premier quelque soit n>1 au contraire les nombres de la forme 3n+1 et 3n-1 sont peut être premiers.
Les multiples de 4 sont déjà exclus puisqu'on a déjà traité le cas des multiples de 2 et tout nombre divisible par 4 est divisible par 2, la démonstration est triviale.
En combinant ces deux propriétés nous concluons que seuls les nombres de la forme 6n-1 et 6n+1 sont potentiellement premiers, se sont les seuls que l'on doit tester, à ces nombres peut être premiers nous devons ajouter 2 et 3.

Code Function Premier

'Pour une fonction qui teste le nombre n

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 &#233;tant un entier naturel)
   '      =k*k'*p'
   'donc k est un diviseur de n et k>1 et k=2
   'n=p*p'
   'et p
   'donc p*p   
   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 n donc premier>
   End If
Next i
End Function

Le nombre de calculs a cette étape a environ été divisé par 25 environ.

Sans ces connaissances pour savoir si le nombre 101 est premier il faut faire 98 calculs, soyons modestes 47 calculs suffisent car lorsqu'on dépasse la moitié on est en dessous de 2 et on voit bien que le nombre ne peut plus être premier.
Maintenant sqr(101) < 11. Jusqu'à 11 on ne divisera que par 5 et 7 donc seulement deux nombres suffisent à dire que 101 est premier avec certitude.
Ça c'est de l'optimisation!

Propriétés

  • Tout entier n composé se décompose de manière unique en produit de nombres premiers
  • Soit n un entier composé n=p1a1*p2a2*...*pnan alors tout les diviseurs d de n s'écrivent sous la forme d = p1b1*p2b2*...*pnbn
Ce document intitulé « Nombres premiers » issu de CodeS SourceS (codes-sources.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
Infos systeme avec vb.net
Initiation msgbox() et inputbox()
Rejoignez-nous