Le moyen le plus rapide de tester si un nombre est premier avec Python

Question

J'essaie d'obtenir un moyen rapide de déterminer si un nombre est premier en utilisant Python.

J'ai deux fonctions pour le faire. Les deux retournent soit Vrai ou Faux.

Fonction isPrime1 est très rapide à renvoyer False est un nombre n'est pas un nombre premier. Par exemple avec un grand nombre. Mais il est lent à tester True pour les grands nombres premiers.

Fonction isPrime2 est plus rapide en retournant True pour les nombres premiers. Mais si un nombre est grand et n'est pas premier, cela prend trop de temps pour retourner une valeur. La première fonction fonctionne mieux avec ça.

Comment puis-je trouver une solution qui pourrait rapidement retourner False pour un grand nombre qui n'est pas premier et fonctionnerait rapidement avec un grand nombre qui est premier?

`

def isPrime1(number): #Works well with big numbers that are not prime 
    state = True 
    if number <= 0: 
     state = False 
     return state 
    else:   
     for i in range(2,number): 
      if number % i == 0: 
       state = False 
       break 
     return state 

def isPrime2(number): #Works well with big numbers that are prime 
    d = 2 
    while d*d <= number: 
     while (number % d) == 0:    
      number //= d 
     d += 1 
    if number > 1:  
     return True 
    else: 
     return False` 

Answer 1

tests de primalité est un sujet très délicat. Avant de tenter d'accélérer votre code, essayez de vous assurer que cela fonctionne comme prévu. Je vous suggère de commencer avec des algorithmes très simples, puis de construire à partir de là.

D'intérêt, isPrime2 est défectueux. Il retourne vrai pour 6, 10, 12, ...

lignes 3 à 6 sont très révélateur

while d*d <= number: 
    while (number % d) == 0:    
     number //= d 
    d += 1 

Lorsqu'un facteur d number se trouve, le numéro est mis à jour number = number // d et à la fin de la boucle while, si le numéro> 1 vous revenez True

Travailler dans le code avec number = 6:

isPrime2(6) 
initialise> number := 6 
initialise> d := 2 
line3> check (2 * 2 < 6)  :True 
line4> check (6 % 2 == 0) :True 
line5> update (number := 6//2) -> number = 3 
line6> update (d : d + 1) -> d = 3 
jump to line3 
line3> check (3 * 3 < 3)  :False -> GOTO line7 
line7> check(number > 1) -> check(3 > 1) :True 
line8> return True -> 6 is prime 

Answer 2

Voici ce que j'ai trouvé

def is_prime(number): 
    # if number is equal to or less than 1, return False 
    if number <= 1: 
     return False 

    for x in range(2, number): 
     # if number is divisble by x, return False 
     if not number % x: 
      return False 
    return True 

Answer 3

La division complète jusqu'à la racine carrée est à peu près la plus simple que vous pouvez penser. Son pire cas est pour les primes, car toutes les divisions doivent être effectuées. Quoi qu'il en soit, jusqu'à un milliard, il n'y a pratiquement pas de temps mesurable (environ 1,2 ms pour 1000000007).

def Prime(n): 
    if n & 1 == 0: 
     return 2 
    d= 3 
    while d * d <= n: 
     if n % d == 0: 
      return d 
     d= d + 2 
    return 0 

Notez que cette version retourne le plus petit diviseur ou 0 plutôt que d'un booléen.

Certaines micro-optimisations sont possibles (comme l'utilisation d'une table d'incréments), mais je ne pense pas qu'elles puissent générer des gains importants.

Il existe des méthodes beaucoup plus sophistiquées et plus rapides disponibles, mais je ne suis pas sûr qu'ils valent la peine pour un si petit n.