NOMBRES PREMIERS

Une première propriété qui est la base de tout.
Un entier naturel est dit premier s'il admet exactement 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

Nous pouvons maintenant nous demander si cet enssemble est fini ou infini ?
Supposons que L'enssemble 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 contradicrion donc J est premier
De plus J>q donc q n'est pas le plus grand nombre premier. D'où une contradiction
Donc l'enssemble des nombres premiers est infini.

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 kD'où une contradiction car k est plus petit que le plus petit diviseur de n et k
divise n, donc p est premier
n=p*p' et p
donc p²
et p²ce qui éqivaut à p
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.

'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 crtains 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 (u_n) la suite des nombres pairs    u_n= 2n. nous savons que lorsque n>1 u_n n'est pas premier quel que soit n. les
nombres de la forme 2n+1 sont peut être premiers.
Nous pouvons traiter de la sorte les multiples de chaques nombres les multiples de 3 sont a exclure pour les memes
raisons u_n= 3n, u_n n'est pas remier quel que 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éja exclus puisqu'un 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 potentielement
premiers, se sont les seuls que l'on doit tester, à ces nombres peut être premiers nous devons ajouter 2 et 3

'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 étant un entier naturel)
   '      =k*k'*p'
   'donc k est un diviseur de n et k>1 et k   '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
   'donc p*p   ' et donc p   'donc si n est un entier composé il existe un diviseur premier de n tel que 2   '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)
   End If

Next i

Le nombre de calculs a cette étape à 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 etre 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. SA C'EST DE L'OPTIMISATION

Propriété
Tout entier n composé se décompose de maniere unique en produit de nombres premiers

Propriété
Soit n un entier composé n=p1^a1*p2^a2*...*pn^an alors tout les diviseurs d de n s'écrivent sous la forme d = p1^b1*p2^b2*...*pn^bn

07 août 2005 09:18:28 :

Ajout de propriétés

07 août 2005 09:30:09 :

erreur dans un exemple de programme

07 août 2005 19:15:07 :

Modification d'un code

09 octobre 2005 18:12:01 :

Modification mise en page

09 décembre 2005 20:18:29 :

Correction du code

10 décembre 2005 15:16:25 :

Mise en page

16 décembre 2005 18:40:29 :

code

25 février 2006 11:44:37 :

Effort de présentation