Ich benutze es gelegentlich selbst, also werde ich es auf Qiita posten (´ ・ ω ・ `)
primes (x) ist eine Methode, die Primzahlen kleiner als x in der Liste speichert. Als Algorithmus wird das Standard "Eratostenes-Sieb" verwendet. Ich denke, der Punkt, an dem kein Filter usw. verwendet wird, kann als Gerät bezeichnet werden.
Als nächstes ist "is_prime (x)" eine Methode, um zu bestimmen, ob die ganze Zahl "x" eine Primzahl ist. Der Algorithmus ist immer noch der Standard "Trial Split". Wir versuchen jedoch, die Effizienz durch die Verwendung von Pseudo-Primzahlen (Zahlen, die nicht durch 2, 3 oder 5 teilbar sind) zu verbessern.
import math
#Gibt eine Liste von Primzahlen größer oder gleich 0 und Ganzzahlen x "kleiner als" zurück.
def primes(x):
if x < 2: return []
primes = [i for i in range(x)]
primes[1] = 0 #1 ist keine Primzahl
#Eratostenes Sieb
for prime in primes:
if prime > math.sqrt(x): break
if prime == 0: continue
for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0
return [prime for prime in primes if prime != 0]
#Bestimmen Sie, ob die Ganzzahl x eine Primzahl ist
def is_prime(x):
if x < 2: return False #Es gibt keine Primzahlen unter 2
if x == 2 or x == 3 or x == 5: return True # 2,3,5 ist eine Primzahl
if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,Vielfache von 5 sind zusammengesetzte Zahlen
#Testaufteilung:Pseudo-Primzahl(Zahlen, die nicht durch 2, 3 oder 5 teilbar sind)Teilen Sie einen nach dem anderen
prime = 7
step = 4
while prime <= math.sqrt(x):
if x % prime == 0: return False
prime += step
step = 6 - step
return True
if __name__ == '__main__':
print(primes(30)) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
ls = [x for x in range(30) if is_prime(x)]
print(ls) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Recommended Posts