Discussion :

[Chalix]

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

[wiztricks]

Salut,

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

[Chalix]

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

[wiztricks]

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

[flapili]

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"

[marco056]

Va voir sur le site de tyrtamos...
http://www.jpvweb.com/accueil/