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é

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
Eh



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

MessageSujet: Test de primalité   Dim 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


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

MessageSujet: Re: Test de primalité   Dim 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!

_________________
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

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

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




MessageSujet: Re: Test de primalité   Aujourd'hui à 4:04

Revenir en haut Aller en bas
 
Test de primalité
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Le test de Rorschach
» Test de Student !
» test unilatéral vs test bilatéral
» Test de levene sous SPSS
» Corrélation entre 2 séries de données, quel test?

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: