IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

algorithme des nombres premiers


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club
    Inscrit en
    Octobre 2010
    Messages
    109
    Détails du profil
    Informations forums :
    Inscription : Octobre 2010
    Messages : 109
    Points : 36
    Points
    36
    Par défaut algorithme des nombres premiers
    SALU TOUT LE MONDE
    j'ai un exercice d'ALGO j'ai essayé de trouver la solution mais je suis pas sûre.


    EXO
    Construire l'algorithme qui nous donne les N premiers nombres premiers?


    Ma solution
    ALGORITHME nmb_premier;
    Var N, i: entier

    DEBUT

    Lire (N);
    Pour i allant de 1 à N faire
    DPOUR
    Si ( N Mod i ) =/= 0
    DSI
    ecrire (i)
    FSI
    FPOUR
    FIN.
    Veuillez me corriger

  2. #2
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    Bonjour,

    cet algorithme est faux
    - aller de 1 à N ne donne pas les N premiers nombres premiers.
    - N % i =/= 0 permet de savoir si N est divisible par i. Si i varie de 2 à N-1 est qu'aucune valeur de i ne divise N, alors dans ce cas N est premier.
    Corrigez donc en utilisant ma deuxième remarque.

    Pour avoir les N nombres premier, on utilise souvent le crible d'Eratostène.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  3. #3
    Nouveau membre du Club
    Inscrit en
    Octobre 2010
    Messages
    109
    Détails du profil
    Informations forums :
    Inscription : Octobre 2010
    Messages : 109
    Points : 36
    Points
    36
    Par défaut
    Citation Envoyé par ToTo13 Voir le message
    Bonjour,

    cet algorithme est faux
    - aller de 1 à N ne donne pas les N premiers nombres premiers.
    - N % i =/= 0 permet de savoir si N est divisible par i. Si i varie de 2 à N-1 est qu'aucune valeur de i ne divise N, alors dans ce cas N est premier.
    Corrigez donc en utilisant ma deuxième remarque.

    Pour avoir les N nombres premier, on utilise souvent le crible d'Eratostène.
    Merci mais j'ai pas bien compri ta 2 eme remarque?

  4. #4
    Expert éminent Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Points : 7 903
    Points
    7 903
    Par défaut
    Le crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C'est l'ancêtre du crible d'Atkin qui est plus rapide mais plus complexe.
    source : wikipedia
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  5. #5
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Septembre 2007
    Messages
    7 360
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 360
    Points : 23 600
    Points
    23 600
    Par défaut
    Citation Envoyé par sali2801 Voir le message
    Merci mais j'ai pas bien compri ta 2 eme remarque?
    Il faut chercher un peu toi-même, surtout avant de faire remonter ton message (ce qui est proscrit sur ce forum en l'absence d'éléments supplémentaires). Cherche Crible d'Ératosthène sur Wikipédia, tu le trouves immédiatement. Le crible d'Ératosthène est une méthode connue depuis l'antiquité et qui relève du simple bon sens : pour trouver les nombres premiers, on élimine les autres (les multiples).

    Tu commences à 0, puis tu sautes les cases de 2 en 2, en les rayant à chaque fois. Tu élimines ainsi tous les nombres pairs. Ensuite, tu recommences en partant de zéro et tu sautes les cases de trois en trois, toujours en les rayant. Tu élimines ainsi tous les nombres multiples de trois. Et ainsi de suite en sautant de 4 en 4, 5 en 5, etc.

    Toutes les cases que tu n'as pas rayées entre le zéro et la première case où tu sautes sont forcément des nombres premiers.

Discussions similaires

  1. Générer des nombres premiers trés grands
    Par Midou45 dans le forum Mathématiques
    Réponses: 9
    Dernier message: 04/05/2008, 01h20
  2. [débutant]Trouver des nombres premiers
    Par Sébastien L dans le forum Langage
    Réponses: 17
    Dernier message: 19/10/2006, 13h21
  3. Cripter avec des nombres premiers
    Par clovis dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 14/04/2004, 20h10

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo