[CRPE] Nombres premiers
[CRPE] Nombres premiers
bonjour
ma question est la suivante : sachant que l'on définit un nombre premier comme étant un nombre entier naturel qui n'admet que deux diviseurs, lui-même, et 1, peut-on affirmer qu'un nombre premier (en partant du principe qu'on ne le connait pas) est identifiable du fait qu'il n'est ni divisible par 2 (et ses multiples), ni par 3 (et ses multiples), ni par 5, ainsi que l'ensemble des nombres premiers qui le précède ?
je crois qu'il n'existe pas de méthode pour cela, sans passer par les nombres premiers inférieurs, pouvez-vous confirmer, ou infirmer ?
merci
ma question est la suivante : sachant que l'on définit un nombre premier comme étant un nombre entier naturel qui n'admet que deux diviseurs, lui-même, et 1, peut-on affirmer qu'un nombre premier (en partant du principe qu'on ne le connait pas) est identifiable du fait qu'il n'est ni divisible par 2 (et ses multiples), ni par 3 (et ses multiples), ni par 5, ainsi que l'ensemble des nombres premiers qui le précède ?
je crois qu'il n'existe pas de méthode pour cela, sans passer par les nombres premiers inférieurs, pouvez-vous confirmer, ou infirmer ?
merci
Dernière modification par M@rion le jeudi 24 septembre 2009, 07:42, modifié 1 fois.
-
- Modérateur général
- Messages : 8191
- Inscription : vendredi 06 janvier 2006, 15:32
- Statut actuel : Enseignant
- Localisation : Le Mans
- Contact :
Re: [CRPE] exercice nombres premiers
Un entier $n\geqslant2$ est premier s'il n'est divisible par aucun nombre premier $p\leqslant\sqrt n$.
C'est un peu le principe du crible d'Ératosthène ton affaire !
C'est un peu le principe du crible d'Ératosthène ton affaire !
Pas d'aide par MP : les questions sont publiques, les réponses aussi.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
Re: [CRPE] exercice nombres premiers
merci
oui mais ça ça fonctionne pour des nombres relativement petits, mais pour un nombre à quinze chiffres par exemple, comment fait-on en temps limité ?
oui mais ça ça fonctionne pour des nombres relativement petits, mais pour un nombre à quinze chiffres par exemple, comment fait-on en temps limité ?
-
- Modérateur général
- Messages : 8191
- Inscription : vendredi 06 janvier 2006, 15:32
- Statut actuel : Enseignant
- Localisation : Le Mans
- Contact :
Re: [CRPE] Nombres premiers
Un programme à écrire ou déjà écrit (je ne sais pas si Maxima fait cela).
Pas d'aide par MP : les questions sont publiques, les réponses aussi.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
Re: [CRPE] Nombres premiers
merci, donc pour les grands nombres, à moins d'avoir un pc à disposition, pas de solution ?
pour l'exercice 1 page 2 est-ce que ma définition convient ?
pour l'exercice 1 page 2 est-ce que ma définition convient ?
-
- Modérateur général
- Messages : 8191
- Inscription : vendredi 06 janvier 2006, 15:32
- Statut actuel : Enseignant
- Localisation : Le Mans
- Contact :
Re: [CRPE] Nombres premiers
On peut appliquer la méthode du crible à 3737 (avec une calculatrice au besoin)
... si on n'a pas remarqué que : $3737=3700+37=37\times100+37\times1=37\times101$
... si on n'a pas remarqué que : $3737=3700+37=37\times100+37\times1=37\times101$
Pas d'aide par MP : les questions sont publiques, les réponses aussi.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
Re: [CRPE] Nombres premiers
merci mais pour la 1ère question, pour justifier, je peux m'appuyer sur cette définition ou il faut appliquer la méthode du crible directement ?
-
- Modérateur honoraire
- Messages : 6962
- Inscription : mercredi 15 février 2006, 13:18
- Localisation : le havre
- Contact :
Re: [CRPE] Nombres premiers
Il y a des algorithmes efficaces pour prouver qu'un nombre est premier. Il y en a un qui est en temps polynomial en terme de temps de calcul vu comme un fonction de la taille des nombres. Par contre, on pense qu'il n'y a pas d'algorithme permettant de factoriser un nombre en produit de facteurs premiers en un temps qui ne soit pas exponentiel. Ça tombe bien certains algorithmes de cryptage reposent sur cette impossibilité.
Bref c'est un problème compliqué.
Olivier
Bref c'est un problème compliqué.
Olivier
A line is a point that went for a walk. Paul Klee.
Par solidarité, pas de MP.
Par solidarité, pas de MP.
-
- Modérateur général
- Messages : 8191
- Inscription : vendredi 06 janvier 2006, 15:32
- Statut actuel : Enseignant
- Localisation : Le Mans
- Contact :
Re: [CRPE] Nombres premiers
Pour les premiers, on applique les critères de divisibilité habituels par 2, 3, 5, 9.
Pas d'aide par MP : les questions sont publiques, les réponses aussi.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
Tu as apprécié l'aide qui t'a été fournie ? Alors n'hésite pas à rendre la pareille à quelqu'un d'autre.
Un peu d'autopromotion.
-
- Utilisateur chevronné
- Messages : 1172
- Inscription : lundi 21 mai 2007, 13:57
- Statut actuel : Autre
- Localisation : Dordogne
Re: [CRPE] Nombres premiers
Bonjour,
guiguiche a donné la réponse "élémentaire"dans son principe mais lourde à appliquer pour les grands nombres.
Pour des grands nombres, il y a des méthodes permettant d'accélérer au moyen de quelques astuces le crible d'Érastosthène. Cela permet de factoriser en ~1sec des nombres de 15 chiffres. J'ai eu fait de tels programmes en Visual Basic.
Au delà cela nécessite des techniques particulières.
Il faut cependant distinguer la recherche des facteurs premiers ( éventuels ) et déterminer qu'un nombre est premier ou non.
Si l'on connait ses facteurs premiers, on sait immédiatement si le nombre est premier ou non.
Il existe des méthodes prouvant qu'un nombre est ( seulement probablement parfois ) premier ou non sans que l'on connaisse pour autant ses facteurs.
Pour info:
http://www.alpertron.com.ar/ECM.HTM
on peut y factoriser des nombres de plus de 100 chiffres...
guiguiche a donné la réponse "élémentaire"dans son principe mais lourde à appliquer pour les grands nombres.
Pour des grands nombres, il y a des méthodes permettant d'accélérer au moyen de quelques astuces le crible d'Érastosthène. Cela permet de factoriser en ~1sec des nombres de 15 chiffres. J'ai eu fait de tels programmes en Visual Basic.
Au delà cela nécessite des techniques particulières.
Il faut cependant distinguer la recherche des facteurs premiers ( éventuels ) et déterminer qu'un nombre est premier ou non.
Si l'on connait ses facteurs premiers, on sait immédiatement si le nombre est premier ou non.
Il existe des méthodes prouvant qu'un nombre est ( seulement probablement parfois ) premier ou non sans que l'on connaisse pour autant ses facteurs.
Pour info:
http://www.alpertron.com.ar/ECM.HTM
on peut y factoriser des nombres de plus de 100 chiffres...
J'ai le virus des sciences, ça se soigne ?
Re: [CRPE] Nombres premiers
Merci à vous trois pour vos réponses :D
C'est intéressant ! cela doit passionner les cryptographes
Framboise, peux-tu (vous ) m'expliquer un peu comment on procède pour améliorer la méthode du crible d'Eratosthène s'il te plait ?
C'est intéressant ! cela doit passionner les cryptographes
Framboise, peux-tu (vous ) m'expliquer un peu comment on procède pour améliorer la méthode du crible d'Eratosthène s'il te plait ?
-
- Utilisateur chevronné
- Messages : 1172
- Inscription : lundi 21 mai 2007, 13:57
- Statut actuel : Autre
- Localisation : Dordogne
Re: [CRPE] Nombres premiers
Le crible peut être considéré de diverses manières.
- Le crible très naïf: on teste tous les nombres jusqu'au nombre à factoriser
- on voit très vite que l'on peut s'arrêter à la racine carrée du nombre à factoriser compte tenu que l'on balaye tous les nombres depuis 2 jusqu'à la racine carrée.
- on voit ensuite que l'on peut se limiter aux nombres impairs ( donc non multiples de 2 ).
- on peut l'étendre aux nombres non multiples de 3, 5, 7, ...
- à la limite, on teste avec tous les nombres premiers jusqu'à la racine carrée.
Vu que tester avec strictement les nombres premiers est très lourd, la liste étant lourde à générer/manipuler, il est pratique de se limiter aux nombres non multiples des premiers nombres premiers 2, 3, 5, 7,..., plus ces nombres eux-mêmes.
Cela "pollue" ainsi le test de factorisation par un petite proportion de nombres qui ne sont en fait pas premier.
On gagne du temps avec un ordi ainsi tant que l'on prend des petits nombres premiers, mais on arrive très vite à une sorte de saturation où l'on ne gagne plus rien et même régresse au delà. La limite optimale, qui dépend des compilateurs, est autour des facteurs premiers 7 à 23.
Le gain en vitesse par rapport à la méthode naïve, avec arrêt à la racine carrée, est de l'ordre de 5, ce qui reste très modeste.
Cette méthode présente surtout un intérêt pédagogique car d'autres méthodes "pro" de factorisation sont largement plus efficaces
C'est le principe de la Wheel factorization ( -> Google... ).
- Le crible très naïf: on teste tous les nombres jusqu'au nombre à factoriser
- on voit très vite que l'on peut s'arrêter à la racine carrée du nombre à factoriser compte tenu que l'on balaye tous les nombres depuis 2 jusqu'à la racine carrée.
- on voit ensuite que l'on peut se limiter aux nombres impairs ( donc non multiples de 2 ).
- on peut l'étendre aux nombres non multiples de 3, 5, 7, ...
- à la limite, on teste avec tous les nombres premiers jusqu'à la racine carrée.
Vu que tester avec strictement les nombres premiers est très lourd, la liste étant lourde à générer/manipuler, il est pratique de se limiter aux nombres non multiples des premiers nombres premiers 2, 3, 5, 7,..., plus ces nombres eux-mêmes.
Cela "pollue" ainsi le test de factorisation par un petite proportion de nombres qui ne sont en fait pas premier.
On gagne du temps avec un ordi ainsi tant que l'on prend des petits nombres premiers, mais on arrive très vite à une sorte de saturation où l'on ne gagne plus rien et même régresse au delà. La limite optimale, qui dépend des compilateurs, est autour des facteurs premiers 7 à 23.
Le gain en vitesse par rapport à la méthode naïve, avec arrêt à la racine carrée, est de l'ordre de 5, ce qui reste très modeste.
Cette méthode présente surtout un intérêt pédagogique car d'autres méthodes "pro" de factorisation sont largement plus efficaces
C'est le principe de la Wheel factorization ( -> Google... ).
J'ai le virus des sciences, ça se soigne ?
Re: [CRPE] Nombres premiers
merci beaucoup :D
pour la racine carrée on en avait déjà parlé à propos d'un exercice il me semble (avec Olivier)
les compilateurs ?
pour la racine carrée on en avait déjà parlé à propos d'un exercice il me semble (avec Olivier)
les compilateurs ?
-
- Utilisateur chevronné
- Messages : 1172
- Inscription : lundi 21 mai 2007, 13:57
- Statut actuel : Autre
- Localisation : Dordogne
Re: [CRPE] Nombres premiers
Oui au début du fil de discussion, je l'ai repris pour mémoire afin de montrer la graduation des méthodes.pour la racine carrée on en avait déjà parlé à propos d'un exercice il me semble (avec Olivier)
J'ai fait des essais avec différents compilateurs et interpréteurs:les compilateurs ?
Microsoft C7.0
QBASIC
UBASIC
Visual C 6.0
Visual Basic 6.0
avec des performances très variables.
C'est un peu ancien vu que cela fait quelques années que j'ai fait cela.
J'ai le virus des sciences, ça se soigne ?
-
- Sujets similaires
- Réponses
- Vues
- Dernier message