[GO] Primzahl 2 in Python

Fortsetzung von Prime in Python und Prime in Haskell 2. Es war unklar über den Iterator und den Generator, also habe ich versucht, eine Primzahl zu generieren.

Dies ist die, die ich normalerweise sehe.

from itertools import ifilter, count, dropwhile
def sieve():
  g = count(2)
  while True:
    prime = g.next()
    yield prime
    g = ifilter(lambda x, prime=prime: x % prime, g)


first_prime_GE_sieve = (lambda n , ps = sieve() : 
  (dropwhile( lambda x : x < n, ps ) ).next()
)
    
print first_prime_GE_sieve(52951)

#Ergebnis
52951

(Alle Ergebnisse sind die maximale Anzahl, die paiza.io ohne Zeitüberschreitung berechnen kann. Nicht immer gleich, aber als Maß für die Geschwindigkeit.)

Das war's. Während der Ausgabe einer Primzahl fühlt es sich an, als würde man einen Iterator mit unendlicher Länge durchsehen. Gut gemacht.

Sobald Sie den Inhalt verstanden haben, werden Sie feststellen, dass er mit dem Code des Kommentars übereinstimmt, den Sie oben erhalten haben. Nur der Unterschied zwischen einer Funktion und einem Objekt.

Ist es nicht zu schnell?

Wie man das Viertel Haskell macht.

primes :: Integral a => [a]
primes = map fromIntegral $ [2, 3] ++ primes'

primes'  = [5] ++ recursivePrimes 1 7 primes'

recursivePrimes m s (p : ps) = 
  zonedPrimes m s p ++ recursivePrimes (m * p) (p * p) ps

zonedPrimes m s p = 
  [n | n <- croppedPrimables s p, gcd m n == 1] 

croppedPrimables s p = 
  [x + y | x <- [s, s + 6 .. p * p - 6], y <- [0, 4]]
  
main = print . take 1 . dropWhile (<24684009) $ primes

--Ergebnis
[24684013]

Es ist so transformiert, dass Sie es leicht verstehen können. Das Original ist hier.

Es fühlt sich an, als wäre es nach und nach berechnet und angehäuft. Es ist ziemlich schnell.

Ich werde es dort bringen.

Versuchen wir diesen Algorithmus in Python.

from fractions import gcd
from itertools import chain, tee, dropwhile

cropped_primables = (lambda s, p :
  [x + y for x in xrange(s,p * p - 5, 6) for y in [0, 4]]
)

zoned_primes = (lambda m, s, p :
  [n for n in cropped_primables(s, p) if gcd(m, n) == 1]
)

def primes() :
 
  primes_list = [2, 3, 5]
  last_prime = primes_list[-1] 
  primes_iter = iter(primes_list)

  seeds_iter = iter([])
  m = 1
  s = 7
  p = 5

  while True :
    prime = primes_iter.next()
    yield prime

    if prime == last_prime :
      primes_list = zoned_primes(m, s, p)
      last_prime = primes_list[-1]
      
      it1, it2 = tee(primes_list)
      primes_iter = it1
      seeds_iter = chain(seeds_iter, it2)
      
      m = m * p
      s = p * p
      p = seeds_iter.next()

first_prime_GE = (lambda n , ps = primes() : 
  (dropwhile( lambda x : x < n, ps ) ).next()
)
    
print first_prime_GE(3003079)

#Ergebnis
3003079

Haskell verwendet eine verzögerte Auswertung. Was tun mit Python?

Als Algorithmus ist es jedoch nur erforderlich, die nächste Primzahl zu kennen. Daher habe ich einen Iterator separat entwickelt, um einen Wert zurückzugeben und eine Primzahl intern zu berechnen.

Übrigens ist es einfach, aber wenn Sie versuchen einmal ausführen und die Zeit messen mit dem Argument 100000 für IDLE

>>> measure_t(first_prime_GE,100000)
2.5987625122070312e-05

Etwa 0,026 Millisekunden.

Am Anfang

>>> measure_t( first_prime_GE_sieve,100000)
16.222843885421753

Über 16 Sekunden.

Ist es nicht ziemlich schnell?

Nachtrag

Ich habe versucht, den oben genannten Laufzeitfehler zu vermeiden, aber ist das normalerweise so?

# coding: utf-8
from fractions import gcd
from itertools import chain, tee, dropwhile

cropped_primables = (lambda s, p :
  (x + y for x in xrange(s,p * p - 5, 6) for y in [0, 4])
)

zoned_primes = (lambda m, s, p :
  (n for n in cropped_primables(s, p) if gcd(m, n) == 1)
)

def primes() :
  primes_iter = iter([2, 3, 5])

  seeds_iter = iter([])
  m = 1
  s = 7
  p = 5

  while True :
    try :
      prime = primes_iter.next()
      
    except StopIteration :
      primes_base_iter = zoned_primes(m, s, p)
      
      it1,it2 = tee(primes_base_iter)
      primes_iter = it1
      seeds_iter = chain(seeds_iter, it2)
      
      m = m * p
      s = p * p
      p = seeds_iter.next()
      
    else :   
      yield prime

first_prime_GE = (lambda n , ps = primes() : 
  (dropwhile( lambda x : x < n, ps ) ).next()
)

print first_prime_GE(2728100)

##Ergebnis
2728129

Geändert, um StopIteration abzufangen und zu verarbeiten. Geändert zu Iterator anstelle von Array.

Es sieht ordentlich aus. Aber es scheint etwas spät zu sein.

Ebenso, wenn Sie die Ausführungszeit messen

>>> measure_t(first_prime_GE,100000)
3.409385681152344e-05

0,034 Millisekunden.