Maths Cuicui, l'envolée mathématique

forum gratuit d'entraide mathématique de la 6ème à la 2ème année de licence
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez
 

 Test de primalité

Aller en bas 
AuteurMessage
Eh



Masculin Nombre de messages : 237
Localisation : France
Date d'inscription : 08/02/2009

Test de primalité Empty
MessageSujet: Test de primalité   Test de primalité EmptyDim 6 Déc - 17:41

Salut Cuicui !

J'me suis demandé : comment se fait-il qu'il suffise de chercher les diviseurs premiers inférieurs à √n pour montrer qu'un entier n est premier, ou non ?

Pourquoi √n ?
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Blagu'cuicui
Admin'cuicui
Blagu'cuicui

Masculin Nombre de messages : 5010
Age : 33
Localisation : Bretagne (35)
Date d'inscription : 03/09/2007

Test de primalité Empty
MessageSujet: Re: Test de primalité   Test de primalité EmptyDim 6 Déc - 20:51

Bonsoir Natty,

Alors dans un premier temps, on sait qu'on peut arrêter les test lorsqu'on arive à un nombre premier qui est supérieur ou égale à n/2 pour montrer que n est premier. Ceci est plus simple à voir car si on considère un nombre premier plus grand que n/2, on peut voir que n/2>n/(n/2)>2. Et par conséquent, le resultat de la division sera forcément un nombre entre 2 et n/2 qu'on a donc déjà testé!

Maintzenant, on peut en effet faire mieux en disant qu'on peut arrêter les tests lorsqu'on a testé tous les nombres premiers inférieurs ou égale à √n. C'est à dire que si on testait un nombre supérieur à √n, nous pouvons affirmer qu'il ne divisera pas n.

Alors comment voir cela?

Supposons que n=p*q

Par conséquent, si on suppose que p et q sont supérieurs strictement à √n (tous les deux!) alors p*q>n

Contradiction car p*q=n

Par conséquent, p ou q est inférieur ou égale à √n. Donc il existe un diviseur premier de p par exemple qui divisera donc n.

En conclusion, il suffit de tester la divisibilité des nombres premiers inférieurs ou égaux à √n.


Est-ce que c'est plus claire ainsi?

Bon courage!

_________________
Test de primalité Blagu_cuicui
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://www.maths-cuicui.fr
Eh



Masculin Nombre de messages : 237
Localisation : France
Date d'inscription : 08/02/2009

Test de primalité Empty
MessageSujet: Re: Test de primalité   Test de primalité EmptyMer 16 Déc - 17:39

Merci Smile
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Contenu sponsorisé




Test de primalité Empty
MessageSujet: Re: Test de primalité   Test de primalité Empty

Revenir en haut Aller en bas
 
Test de primalité
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Niveau de stress et son orientation : test
» test Khi2
» Test statistique pour une régression non linéaire
» test du khi 2
» Test de mann whitney avec STATISTICA

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Maths Cuicui, l'envolée mathématique :: L'envolée du Lycée GT, Pro et du CAP :: Entre-aide pour la Terminale G, T et Pro :: Exercices de cours-
Sauter vers: