Controleren of een getal een priemgetal is in Python

Ik heb de volgende code geschreven, die moet controleren of het ingevoerde nummer een priemgetal is of niet, maar er is een probleem waar ik niet uitkom:

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()

Als het ingevoerde getal geen priemgetal is, wordt “geen priemgetal” weergegeven, zoals het hoort, maar als het getal een priemgetal is, wordt er niets weergegeven. Hoe kan ik dit oplossen?

Antwoord 1, autoriteit 100%

Hier is mijn kijk op het probleem:

from math import sqrt
from itertools import count, islice
def is_prime(n):
    return n > 1 and all(n % i for i in islice(count(2), int(sqrt(n)-1)))

Dit is een heel eenvoudig en beknopt algoritme en daarom is het niet bedoeld om in de buurt te komen van het snelste of meest optimale algoritme voor priemcontrole. Het heeft een tijdcomplexiteit van O(sqrt(n)). Ga naar hiervoor meer informatie over goed uitgevoerde priemtests en hun geschiedenis.

Uitleg

Ik ga je wat inzicht geven in die bijna esoterische enkele regel code die op priemgetallen controleert:

• Allereerst is het gebruik van range()in Python 2 echt een slecht idee, omdat het een lijst met nummers zal maken, die veel geheugen gebruikt. Met xrange()is beter, omdat het een generator creëert, die alleen de eerste argumenten die u verstrekt, en genereert elk getal on-the-fly. Als u gebruikt
  Python 3, range()is standaard geconverteerd naar een generator. Trouwens, dit is nog steeds niet de beste oplossing: proberen te bellen xrange(n)voor sommige nzodanig dat n > 231-1(Die is de maximale waarde voor een C long) verhoogt OverflowError. Daarom is de beste manier om een ​​bereikgenerator te maken 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
  

• U hoeft niet echt helemaal tot op nte gaan als u wilt controleren of neen priemgetal is. U kunt de tests drastisch verminderen en alleen controleren van 2 naar √(n)(vierkantswortel van n). Hier is een voorbeeld:

  Laten we alle Divisors of n = 100vinden, en vermeld ze in een tabel:

  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
  

  U zult gemakkelijk opmerken dat, na de vierkantswortel van n, alle delicanten die we vinden, daadwerkelijk al gevonden. Bijvoorbeeld, 20is al gevonden met het doen van 100/5. De vierkantswortel van een nummer is het exacte middelpunt waar de divisors die we vonden beginnen te worden gedupliceerd. Daarom, om te controleren of een nummer prime is, hoeft u alleen maar te controleren van 2 naar sqrt(n).

• Waarom sqrt(n)-1DAN, EN NIET ALLEEN sqrt(n)? Dat is alleen omdat het tweede argument verstrekt aan itertools.islice()het aantal iteraties is om uit te voeren. islice(count(a), b)Stopt na bITERATIES. Dat is de reden waarom:

  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
  

• De functie all(...)is hetzelfde van de volgende:

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

  Het controleert letterlijk voor alle elementen in de iterable, retourneren van Falsewanneer een van hen evalueert naar False(die voor een integer betekent alleen als het nul is). Waarom gebruiken we het dan? Allereerst hoeven we geen extra indexvariabele te gebruiken (zoals we zouden doen met een lus), behalve dat: alleen voor concision, er is geen echte behoefte aan, maar het ziet er veel minder omvangrijk uit om alleen te werken een enkele regel code in plaats van verschillende geneste lijnen.

Uitgebreide versie

Ik voeg een “uitgepakte” versie van de functie is_prime()toe om het gemakkelijker te begrijpen en te lezen:

from math import sqrt
from itertools import count, islice
def is_prime(n):
    if n < 2:
        return False
    for number in islice(count(2), int(sqrt(n) - 1)):
        if n % number == 0:
            return False
    return True

Antwoord 2, autoriteit 61%

Er zijn veel efficiënte manieren om priemgetallen te testen (en dit is er niet één van), maar de lus die je hebt geschreven kan beknopt worden herschreven in Python:

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

Dat wil zeggen, a is een priemgetal als alle getallen tussen 2 en a (niet inclusief) een rest geven die niet nul is wanneer ze worden gedeeld in a.

Antwoord 3, autoriteit 30%

Dit is de meest efficiënte manier om te zien of een getal een priemgetal is, als je maar een paar vragen hebt. Als je veel getallen vraagt of ze priemgetallen zijn, probeer dan Zeef van 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

Antwoord 4, autoriteit 13%

Als aeen priemgetal is, zal de while x:in je code voor altijd blijven bestaan, aangezien xTrue.

Dus waarom is dat whiledaar?

Ik denk dat je de for-lus wilde beëindigen toen je een factor vond, maar niet wist hoe, dus je hebt dat terwijl toegevoegd omdat het een voorwaarde heeft. Dus hier is hoe je het doet:

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"