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
    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
    Expert éminent sénior
    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
    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
    Expert éminent sénior
    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 éclairé
    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é
    Va voir sur le site de tyrtamos...
    http://www.jpvweb.com/accueil/
    Pas d'aide par mp.

###raw>template_hook.ano_emploi###