[CRPE] Nombres premiers

Aide à la résolution d'exercices ou de problèmes dont le niveau n'entre pas dans les catégories précédentes (pour le primaire par exemple).

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

[CRPE] Nombres premiers

Messagepar M@rion » Mardi 22 Septembre 2009, 14:59

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 édition par M@rion le Jeudi 24 Septembre 2009, 06:42, édité 1 fois.
M@rion
Giga-utilisateur
 
Messages: 594
Inscription: Lundi 07 Avril 2008, 16:28
Statut actuel: Actif et salarié

Publicité

Re: [CRPE] exercice nombres premiers

Messagepar guiguiche » Mardi 22 Septembre 2009, 15:12

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.
guiguiche
Modérateur
 
Messages: 8071
Inscription: Vendredi 06 Janvier 2006, 15:32
Localisation: Le Mans
Statut actuel: Actif et salarié | Enseignant

Re: [CRPE] exercice nombres premiers

Messagepar M@rion » Mardi 22 Septembre 2009, 15:28

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é ?
M@rion
Giga-utilisateur
 
Messages: 594
Inscription: Lundi 07 Avril 2008, 16:28
Statut actuel: Actif et salarié

Re: [CRPE] Nombres premiers

Messagepar guiguiche » Mardi 22 Septembre 2009, 16:03

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.
guiguiche
Modérateur
 
Messages: 8071
Inscription: Vendredi 06 Janvier 2006, 15:32
Localisation: Le Mans
Statut actuel: Actif et salarié | Enseignant

Re: [CRPE] Nombres premiers

Messagepar M@rion » Mardi 22 Septembre 2009, 16:16

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 ?
M@rion
Giga-utilisateur
 
Messages: 594
Inscription: Lundi 07 Avril 2008, 16:28
Statut actuel: Actif et salarié

Re: [CRPE] Nombres premiers

Messagepar guiguiche » Mardi 22 Septembre 2009, 16:42

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.
guiguiche
Modérateur
 
Messages: 8071
Inscription: Vendredi 06 Janvier 2006, 15:32
Localisation: Le Mans
Statut actuel: Actif et salarié | Enseignant

Re: [CRPE] Nombres premiers

Messagepar M@rion » Mardi 22 Septembre 2009, 17:15

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 ?
M@rion
Giga-utilisateur
 
Messages: 594
Inscription: Lundi 07 Avril 2008, 16:28
Statut actuel: Actif et salarié

Re: [CRPE] Nombres premiers

Messagepar rebouxo » Mardi 22 Septembre 2009, 17:34

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
rebouxo
Modérateur
 
Messages: 6952
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Re: [CRPE] Nombres premiers

Messagepar guiguiche » Mardi 22 Septembre 2009, 17:46

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.
guiguiche
Modérateur
 
Messages: 8071
Inscription: Vendredi 06 Janvier 2006, 15:32
Localisation: Le Mans
Statut actuel: Actif et salarié | Enseignant

Re: [CRPE] Nombres premiers

Messagepar Framboise » Mardi 22 Septembre 2009, 19:21

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 ?
Framboise
Téra-utilisateur
 
Messages: 1154
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: [CRPE] Nombres premiers

Messagepar M@rion » Mardi 22 Septembre 2009, 19:38

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 ?
M@rion
Giga-utilisateur
 
Messages: 594
Inscription: Lundi 07 Avril 2008, 16:28
Statut actuel: Actif et salarié

Re: [CRPE] Nombres premiers

Messagepar Framboise » Mercredi 23 Septembre 2009, 08:01

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 ?
Framboise
Téra-utilisateur
 
Messages: 1154
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: [CRPE] Nombres premiers

Messagepar M@rion » Jeudi 24 Septembre 2009, 06:42

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 ?
M@rion
Giga-utilisateur
 
Messages: 594
Inscription: Lundi 07 Avril 2008, 16:28
Statut actuel: Actif et salarié

Re: [CRPE] Nombres premiers

Messagepar Framboise » Jeudi 24 Septembre 2009, 08:02

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 ?
Framboise
Téra-utilisateur
 
Messages: 1154
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: [CRPE] Nombres premiers

Messagepar M@rion » Jeudi 24 Septembre 2009, 16:21

merci pour toutes ces explications :D
M@rion
Giga-utilisateur
 
Messages: 594
Inscription: Lundi 07 Avril 2008, 16:28
Statut actuel: Actif et salarié


Retourner vers Exercices et problèmes : Autres niveaux

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 1 invité