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

Calcul scientifique Python Discussion :

Test de Primalité


Sujet :

Calcul scientifique Python

  1. #1
    Candidat au Club
    Homme Profil pro
    Lycéen
    Inscrit en
    janvier 2017
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : janvier 2017
    Messages : 4
    Points : 4
    Points
    4
    Par défaut Test de Primalité
    Hello, j'aurais besoin d'aide, je cherche à faire un programme effectuant un test de primalité (donc la vérification si un nombre de donné est premier ou non).

    Evidemment en faire un tout simple est relativement facile, cependant je cherche à en faire un performant qui pourra me résoudre plus rapidement des grosses valeurs comme avec les nombre de Mersenne du type 2^31 - 1, qui prend plusieurs secondes à être effectué avec mon code actuel.

    Voilà mon code pour l'instant :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    def est_premier(n):
        i = 2
     
        while i < n and n % i != 0 :
            i = i + 1
        if i == n:
            return(True)
        else:
            return(False)
    Merci à ceux qui m'aideront

  2. #2
    Modérateur

    Homme Profil pro
    Architecte technique
    Inscrit en
    juin 2008
    Messages
    14 485
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Architecte technique
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 14 485
    Points : 24 505
    Points
    24 505
    Par défaut
    Salut,

    Citation Envoyé par Chalix Voir le message
    Merci à ceux qui m'aideront
    Si vous cherchez un algorithme, vous n'êtes pas dans le bon forum.
    Ceci dit, entrez "test de primalité" sur un moteur de recherche vous donnerait des pistes comme par exemple cet article de wikipedia.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  3. #3
    Candidat au Club
    Homme Profil pro
    Lycéen
    Inscrit en
    janvier 2017
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : janvier 2017
    Messages : 4
    Points : 4
    Points
    4
    Par défaut
    Ah mince, je pensais etre au bon endroit, j'ai pas mal cherché sur internet mais ce ne sont pas des algorithmes suffisament compact et rapide à exécuter

  4. #4
    Modérateur

    Homme Profil pro
    Architecte technique
    Inscrit en
    juin 2008
    Messages
    14 485
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Architecte technique
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 14 485
    Points : 24 505
    Points
    24 505
    Par défaut
    Citation Envoyé par Chalix Voir le message
    Ah mince, je pensais etre au bon endroit, j'ai pas mal cherché sur internet mais ce ne sont pas des algorithmes suffisament compact et rapide à exécuter
    C'est pas pour rien que les algorithmes de cryptages les utilisent: çà prend des plombes pour démontrer que... et qu'on attend (avec inquiétude) la mise au point d'ordinateurs quantiques.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  5. #5
    Membre averti
    Homme Profil pro
    BTS SNIR (système numérique option info & réseau)
    Inscrit en
    mai 2017
    Messages
    302
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Saône et Loire (Bourgogne)

    Informations professionnelles :
    Activité : BTS SNIR (système numérique option info & réseau)

    Informations forums :
    Inscription : mai 2017
    Messages : 302
    Points : 365
    Points
    365
    Par défaut
    Pour commencer vous pouvez regarder la parité du nombre(n), s'il est pair pas besoin d'aller plus loin, de même s'il est divisible par 3, 9, 5, ect avec les critères de divisibilité. (bon ok ses cas sont résolus dès les premiers tours de boucle, mais ça a son importance pour la dernière partie)

    Si n n'est divisible par aucun de ses nombres alors il faut regarder si n est divisible par k où k est compris entre 3 et racine de n (arrondi au supérieur).


    À partir d'ici ce n'est qu'une spéculation mais je suppose que vérifier si k est divisible par 5 est moins coûteux que de vérifier si n l'est, donc pour allez encore un peu plus loin si k est divisible par 5 et que n ne l'ai pas ce n'est pas la peine de regarde si n est divisible par 5.

    Je n'ai pas plus d'idée que ça avec du python "de base"

  6. #6
    Membre expérimenté
    Homme Profil pro
    Enseignant
    Inscrit en
    juin 2013
    Messages
    1 109
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : juin 2013
    Messages : 1 109
    Points : 1 500
    Points
    1 500
    Par défaut
    Va voir sur le site de tyrtamos...
    http://www.jpvweb.com/accueil/
    Pas d'aide par mp.

Discussions similaires

  1. Test de primalité.
    Par kaari kosaku dans le forum Mathématiques
    Réponses: 1
    Dernier message: 27/04/2009, 12h14
  2. Test de primalité
    Par le marocain dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 23/10/2007, 11h26
  3. [débutant] test de primalité
    Par grand_prophete dans le forum C
    Réponses: 14
    Dernier message: 08/10/2006, 13h32
  4. tests de primalité
    Par 123quatre dans le forum C
    Réponses: 2
    Dernier message: 20/12/2005, 10h55
  5. [Algo] Test de primalité
    Par Khorne dans le forum Mathématiques
    Réponses: 10
    Dernier message: 04/04/2004, 11h30

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