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

Langage Pascal Discussion :

Déterminer si un nombre est premier


Sujet :

Langage Pascal

  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    4
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 4
    Points : 2
    Points
    2
    Par défaut Déterminer si un nombre est premier
    Bonsoir,

    J'ai déjà tenté quelques recherches mais en vain alors je viens poser ma question ici : comment peut-on déterminer si un nombre est premier ?

    En fait j'ai un tableau qui contient des entiers compris entre 1 et 1000 et il ne faut garder que les nombres premiers.

    Je n'ai aucune idée sur la façon dont il faut procéder .

    Merci d'avance,

  2. #2
    Membre éclairé Avatar de Tuxico
    Profil pro
    Étudiant
    Inscrit en
    Août 2003
    Messages
    662
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2003
    Messages : 662
    Points : 770
    Points
    770
    Par défaut
    ben tu parcours le tableau le tableau et sur chaque case tu regardes d'abbord si il est pair ou non, si il l'est (mis a part 2) il ne sera pas un nombre premier, donc tu continues si c'est impair tu calcules le pgcd et si le pgcd est le nombre alors c est un nombre premier (pour voir si c est pair : i mod 2 = 0 ) puis chaque fois que tu en trouves un tu le stocke dans un tableau
    ★ Pascal/Java/C/xhtml,css/SQL/Mips
    ★ Linux/unix

  3. #3
    Candidat au Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    4
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 4
    Points : 2
    Points
    2
    Par défaut
    Merci beaucoup.
    Je vais tester !

  4. #4
    Membre confirmé
    Homme Profil pro
    .
    Inscrit en
    Juin 2002
    Messages
    239
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : .
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2002
    Messages : 239
    Points : 567
    Points
    567
    Par défaut
    La méthode la plus simple pour trouver les nombres premiers compris entre 1 et un entier n est connue sous le nom de " crible d'Eratosthène ".

    Cette méthode est expliquée à l'adresse :
    http://perso.wanadoo.fr/therese.eveilleau/pages/truc_mat/pratique/textes/crible_an.htm

  5. #5
    Membre expert
    Avatar de Eric Sigoillot
    Inscrit en
    Mars 2002
    Messages
    1 212
    Détails du profil
    Informations personnelles :
    Âge : 39

    Informations forums :
    Inscription : Mars 2002
    Messages : 1 212
    Points : 3 369
    Points
    3 369
    Par défaut
    De nombreuses méthodes existent pour déterminer si un nombre est prermier ou non, mais le principal problème dans ce genre de cas est le temps que l'on souhaite accorder à la détermination.

    En effet, utiliser une crible d'Erastostène pour des nombres approchant les 10 chiffres est une catastrophe en terme de performances. Il existe alors de méthodes qui permettent de donner un résultat "probable". Autrement dit, il n'est pas assuré à 100% que le résultat donné soit bon, ie si le nombre n'est pas premier, la méthode peut indiquer que celui-ci l'est. Cependant, dans la majorité des cas, le résultat donné suffit.

    Dans ton cas, les nombres sont compris entre 1 et 1000, il suffit donc de tester que ton nombre n'est pas divisible par l'ensemble des nombres premiers inférieurs à la racine carrée du nombre à tester.

    Par exemple, si tu veux tester si 171 est premier ou non, tu prends sa racine carrée, soit 13 (en nombre entier), tu prends tous les nombres premiers inférieurs ou égaux à 13, et tu testes !

    Tes nombres sont inférieurs à 1000, donc en racine, inférieurs à 32. La liste des nombres premiers de 1 à 32 est vite faite : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 et le compte est bon

    Pour notre exemple, on ne va que jusqu'à 13, soit les nombres : 2, 3, 5, 7, 11 et 13.

    Il suffit de regarder les restes des divisions avec l'opérateur mod :
    171 mod 2 = 1
    171 mod 3 = 0

    Donc 171 est divisible par 3. En effet, 171 = 59 * 3. C'est terminé, on sait que 171 n'est pas premier.


    La méthode que je t'ai expliquée ici n'est sûrement pas très performante, mais pour de petits nombres, elle suffit amplement.

    @++
    Règles du forum
    F.A.Q Pascal

    Pour me joindre (aucune question technique, merci)

  6. #6
    Candidat au Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    4
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 4
    Points : 2
    Points
    2
    Par défaut
    Merci pour vos réponses.

    J'avais fait une recherche sur Wikipédia et j'ai laissé tombé parce qu'on a pas vu l'approche probabiliste.

    Je demanderai au prof pour voir .

    Hdd34, j'ai compris ta méthode.
    Par contre, est-ce qu'on peut déterminer laquelle est "la mieux" entre la tienne et celle de Tuxico ?

  7. #7
    Membre éclairé Avatar de Tuxico
    Profil pro
    Étudiant
    Inscrit en
    Août 2003
    Messages
    662
    Détails du profil
    Informations personnelles :
    Âge : 36
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2003
    Messages : 662
    Points : 770
    Points
    770
    Par défaut
    la sienne j'avais complètement oubli cette méthode ^^ (alalala la fatigue du blocus ^^)
    ★ Pascal/Java/C/xhtml,css/SQL/Mips
    ★ Linux/unix

  8. #8
    Candidat au Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    4
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 4
    Points : 2
    Points
    2
    Par défaut
    D'accord. Merci pour tout.

    Fandefruit.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Déterminer si un nombre est premier
    Par Weldan dans le forum Pascal
    Réponses: 14
    Dernier message: 29/01/2014, 13h54
  2. comment tester si un nombre est premier en php ?
    Par Shyboy dans le forum Langage
    Réponses: 1
    Dernier message: 09/03/2007, 18h08
  3. Réponses: 9
    Dernier message: 30/01/2007, 22h03
  4. Savoir si un nombre est premier
    Par Jihnn dans le forum Vos contributions VB6
    Réponses: 4
    Dernier message: 11/08/2006, 11h14
  5. Comment savoir si un nombre est premier ?
    Par Extra-Nitro dans le forum Général Python
    Réponses: 9
    Dernier message: 03/01/2006, 15h28

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