Vérifier si un nombre est un nombre premier en Python [dupliquer]

cette question a déjà une réponse ici:

  • Quel est le meilleur algorithme pour vérifier si un nombre est premier? 19 réponses

j'ai écrit le code suivant, qui devrait vérifier si le nombre entré est un nombre premier ou non, mais il y a un problème que je ne pouvais pas passer à travers:

def main():
n = input("Please enter a number:")
is_prime(n)

def is_prime(a):
    x = True 
    for i in (2, a):
            while x:
               if a%i == 0:
                   x = False
               else:
                   x = True


    if x:
        print "prime"
    else:
        print "not prime"

main()

si le nombre entré n'est pas un nombre premier, il affiche" not prime", comme il est supposé l'être, mais si le nombre est un nombre premier, il n'affiche rien. Pourriez-vous m'aider avec ça?

36
demandé sur Marco Bonelli 2010-11-06 20:16:08

8 réponses

Voici mon point de vue sur le problème:

from math import sqrt; from itertools import count, islice

def isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

c'est un algorithme vraiment simple et concis, et donc il n'est pas censé être quoi que ce soit près de la plus rapide ou l'algorithme de vérification de primalité optimale. Il a une complexité de temps de O(sqrt(n)) . sur la Tête ici pour en savoir plus sur les tests de primalité fait et de leur histoire .


explication

je vais vous donner quelques insides à propos de cette ligne de code presque ésotérique qui vérifiera les nombres premiers:

  • tout d'abord, utiliser range() est vraiment une mauvaise idée, parce qu'il va créer une liste de nombres, qui utilise beaucoup de mémoire. Utiliser xrange() est mieux, car il crée un générateur , qui n'a besoin que de mémoriser les arguments initiaux que vous fournissez, et génère chaque nombre à la volée. Si vous êtes en utilisant Python 3 ou supérieur range() a été converti en Générateur par défaut. Par ailleurs, ce n'est pas la meilleure solution: essayez d'appeler xrange(n) pour certains n tels que n > 231-1 (qui est la valeur maximale pour un C long ) soulève OverflowError . Par conséquent la meilleure façon de créer un générateur d'autonomie est d'utiliser itertools :

    xrange(2147483647+1) # OverflowError
    
    from itertools import count, islice
    
    count(1)                        # Count from 1 to infinity with step=+1
    islice(count(1), 2147483648)    # Count from 1 to 2^31 with step=+1
    islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3
    
  • Vous n'avez pas réellement besoin d'aller tout le chemin jusqu'à n si vous voulez vérifier si n est un nombre premier. Vous pouvez réduire considérablement les tests et vérifier seulement de 2 à √(n) (racine carrée de n ). Voici un exemple:

    trouvons tous les diviseurs de n = 100 , et listons-les dans une table:

     2  x  50 = 100
     4  x  25 = 100
     5  x  20 = 100
    10  x  10 = 100 <-- sqrt(100)
    20  x  5  = 100     
    25  x  4  = 100
    50  x  2  = 100
    

    vous remarquerez facilement que, après le carré racine de n , tous les diviseurs que nous trouvons étaient déjà trouvés . Par exemple 20 a déjà été trouvé faisant 100/5 . La racine carrée d'un nombre est le point médian exact où les diviseurs que nous avons trouvés commencent à être dupliqués. Par conséquent, pour vérifier si un nombre est PREMIER, vous aurez seulement besoin de vérifier de 2 à sqrt(n) .

  • pourquoi sqrt(n)-1 alors, et pas seulement sqrt(n) ? C'est parce que le deuxième argument fourni à itertools.islice l'objet est le nombre d'itérations à exécuter. islice(count(a), b) s'arrête après b itérations . C'est la raison pour laquelle:

    for number in islice(count(10), 2):
        print number,
    
    # Will print: 10 11
    
    for number in islice(count(1, 3), 10):
        print number,
    
    # Will print: 1 4 7 10 13 16 19 22 25 28
    
  • la fonction all(...) est la même que la fonction suivante:

    def all(iterable):
        for element in iterable:
            if not element:
                return False
        return True
    

    littéralement vérifie tous les numéros de la iterable , le retour False lorsqu'un le nombre est évalué à False (ce qui signifie seulement si le nombre est zéro). Pourquoi faisons-nous alors? Tout d'abord, nous n'avons pas besoin d'utiliser une variable d'index supplémentaire (comme nous le ferions en utilisant une boucle), autre que cela: juste pour la concision, il n'y a pas besoin réel de celui-ci, mais il semble beaucoup moins encombrant de travailler avec une seule ligne de code au lieu de plusieurs lignes imbriquées.

Extended version

j'inclus un version "non emballée" de la fonction isPrime() , pour la rendre plus facile à comprendre et à lire:

from math import sqrt
from itertools import count, islice

def isPrime(n):
    if n < 2:
        return False

    for number in islice(count(2), int(sqrt(n) - 1)):
        if n % number == 0:
            return False

    return True
81
répondu Marco Bonelli 2018-06-17 23:49:10

il existe de nombreuses façons efficaces de tester la primalité( et ce n'est pas l'une d'entre elles), mais la boucle que vous avez écrite peut être réécrite de façon concise en Python:

def is_prime(a):
    return all(a % i for i in xrange(2, a))

C'est-à-dire, a est PREMIER si tous les nombres entre 2 et a (non inclus) donnent un reste non-zéro lorsqu'ils sont divisés en a.

66
répondu Marco Bonelli 2018-06-17 23:46:18

C'est la façon la plus efficace de voir si un nombre est PREMIER, si vous avez seulement quelques requêtes. Si vous demandez beaucoup de nombres s'ils sont premier essai tamis de Eratosthenes .

import math

def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False

    sqr = int(math.sqrt(n)) + 1

    for divisor in range(3, sqr, 2):
        if n % divisor == 0:
            return False
    return True
26
répondu Mark 2016-01-18 20:26:07

si a est un prime, alors le while x: dans votre code sera lancé pour toujours, puisque x restera True .

alors pourquoi while ?

je pense que vous vouliez mettre fin à la boucle for quand vous avez trouvé un facteur, mais ne savait pas comment, donc vous avez ajouté que tout en ayant une condition. Alors voici comment vous le faites:

def is_prime(a):
    x = True 
    for i in range(2, a):
       if a%i == 0:
           x = False
           break # ends the for loop
       # no else block because it does nothing ...


    if x:
        print "prime"
    else:
        print "not prime"
8
répondu Jochen Ritzel 2010-11-06 18:46:41
def prime(x):
    # check that number is greater that 1
    if x > 1:
        for i in range(2, x + 1):
            # check that only x and 1 can evenly divide x
            if x % i == 0 and i != x and i != 1:
                return False
        else:
            return True
    else:
        return False # if number is negative
0
répondu Fadyboy 2014-01-22 23:42:45
def is_prime(x):
    n = 2
    if x < n:
        return False
    else:    
        while n < x:
           print n
            if x % n == 0:
                return False
                break
            n = n + 1
        else:
            return True
0
répondu user3732168 2014-06-12 00:16:16
a = input('inter a number: ')
s = 0
if a == 1:  
    print a, 'is a prime'

else : 

    for i in range (2, a ):

        if a%i == 0:
            print a,' is not a prime number'
            s = 'true'
            break

    if s == 0 : print a,' is a prime number'

il a travaillé avec moi tout à l'amende :D

-3
répondu Dhooom 2011-08-09 05:09:08
def isPrime(x):
    if x<2:
        return False
    for i in range(2,x):
        if not x%i:
           return False
    return True  

print isPrime (2)

Vrai

print isPrime (3)

Vrai

print isPrime (9)

Faux

-3
répondu Mesut014 2014-08-19 07:03:30