[CRPE] Nombres premiers

Aide à la résolution d'exercices ou de problèmes de niveau inférieur au baccalauréat.

Modérateur : gdm_sco

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.
M@rion
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 594
Inscription : lundi 07 avril 2008, 17:28

[CRPE] Nombres premiers

Message par M@rion »

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 ? :mrgreen:

merci
Dernière modification par M@rion le jeudi 24 septembre 2009, 07:42, modifié 1 fois.

guiguiche
Modérateur global
Modérateur global
Messages : 8074
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Re: [CRPE] exercice nombres premiers

Message par guiguiche »

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 !
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.

M@rion
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 594
Inscription : lundi 07 avril 2008, 17:28

Re: [CRPE] exercice nombres premiers

Message par M@rion »

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é ?

guiguiche
Modérateur global
Modérateur global
Messages : 8074
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Re: [CRPE] Nombres premiers

Message par guiguiche »

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.

M@rion
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 594
Inscription : lundi 07 avril 2008, 17:28

Re: [CRPE] Nombres premiers

Message par M@rion »

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 ?

guiguiche
Modérateur global
Modérateur global
Messages : 8074
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Re: [CRPE] Nombres premiers

Message par guiguiche »

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$
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.

M@rion
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 594
Inscription : lundi 07 avril 2008, 17:28

Re: [CRPE] Nombres premiers

Message par M@rion »

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 ?

rebouxo
Modérateur global
Modérateur global
Messages : 6962
Inscription : mercredi 15 février 2006, 13:18
Localisation : le havre

Re: [CRPE] Nombres premiers

Message par rebouxo »

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
A line is a point that went for a walk. Paul Klee.
Par solidarité, pas de MP.

guiguiche
Modérateur global
Modérateur global
Messages : 8074
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Re: [CRPE] Nombres premiers

Message par guiguiche »

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.

Framboise
Utilisateur chevronné
Utilisateur chevronné
Messages : 1159
Inscription : lundi 21 mai 2007, 13:57
Statut actuel : Autre
Localisation : Dordogne

Re: [CRPE] Nombres premiers

Message par Framboise »

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...
J'ai le virus des sciences, ça se soigne ?

M@rion
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 594
Inscription : lundi 07 avril 2008, 17:28

Re: [CRPE] Nombres premiers

Message par M@rion »

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 ?

Framboise
Utilisateur chevronné
Utilisateur chevronné
Messages : 1159
Inscription : lundi 21 mai 2007, 13:57
Statut actuel : Autre
Localisation : Dordogne

Re: [CRPE] Nombres premiers

Message par Framboise »

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... ).
J'ai le virus des sciences, ça se soigne ?

M@rion
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 594
Inscription : lundi 07 avril 2008, 17:28

Re: [CRPE] Nombres premiers

Message par M@rion »

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 ?

Framboise
Utilisateur chevronné
Utilisateur chevronné
Messages : 1159
Inscription : lundi 21 mai 2007, 13:57
Statut actuel : Autre
Localisation : Dordogne

Re: [CRPE] Nombres premiers

Message par Framboise »

pour la racine carrée on en avait déjà parlé à propos d'un exercice il me semble (avec Olivier)
Oui au début du fil de discussion, je l'ai repris pour mémoire afin de montrer la graduation des méthodes.
les compilateurs ?
J'ai fait des essais avec différents compilateurs et interpréteurs:
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 ?

M@rion
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 594
Inscription : lundi 07 avril 2008, 17:28

Re: [CRPE] Nombres premiers

Message par M@rion »

merci pour toutes ces explications :D