Technique de divisibilité - crible Eratosthène

Discussions générales concernant les mathématiques et n'entrant pas dans les catégories suivantes.
[participation réservée aux utilisateurs inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
Matt

Technique de divisibilité - crible Eratosthène

Message non lu par Matt »

Bonjour à tous ! Quelqu'un connait-il une technique (claire et où on puisse s'y retrouver facilement) pour connaitre tous les diviseurs d'un nombre SVP ?
Toutes les réponses seront les bienvenues! Merci ! :D
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Message non lu par MB »

C'est un problème complexe pour des nombres relativement grands. Mais pour travailler de manière organisée, on peut éventuellement se baser sur le crible d'Eratosthène qui va permettre de décomposer le nombre en facteurs premiers. Pour chaque nombre premier, on doit effectuer une division euclidienne.
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
P.Fradin

Message non lu par P.Fradin »

On peut se "limiter" à chercher les diviseurs premiers inférieurs ou égaux $\sqrt{n}$ (si $n$ est le nombre en question).
Matt

Message non lu par Matt »

Merci , mais comment appliquer le ... de erastothène ? comment ca fonctionne ? merci !
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Message non lu par MB »

Le crible d'Eratosthène permet tout simplement de lister tous les nombres premiers inférieurs à $\sqrt{n}$ (si $n$ est le nombre à décomposer). Une fois que l'on a cette liste, on effectue la division de $n$ par $2$ pour voir si $n$ est divisible par $2$. Si c'est le cas, on sait que $n = 2 \times n'$ et on recommence (toujours à partir de $2$, disons du nombre premier auquel on en était) avec $n'$. Si ce n'est pas le cas, on passe au nombre premier suivant, $3$ donc ... Si jamais on parcours toute notre liste de nombres premiers sans trouver de diviseur, c'est que $n$ est premier.
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
matt2

Message non lu par matt2 »

merci ! beacoup :D
Répondre