Premier nombre 2 en Python

Poursuite de Prime in Python et Prime in Haskell 2. L'itérateur et le générateur n'étaient pas clairs, j'ai donc essayé de générer un nombre premier.

C'est celui que je vois habituellement.

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)

#résultat
52951

(Tous les résultats sont le nombre maximum qui peut être calculé dans paiza.io sans délai. Pas toujours le même, mais comme un guide pour la vitesse.)

Je vois. Lors de la sortie d'un nombre premier, on a l'impression de passer au crible un itérateur de longueur infinie. Bien joué.

Une fois que vous aurez compris le contenu, vous remarquerez qu'il s'agit du code du commentaire que vous avez reçu ci-dessus. Seule la différence entre une fonction et un objet.

N'est-ce pas trop rapide?

Comment faire le quartier Haskell.

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

--résultat
[24684013]

Il est transformé pour qu'il soit facile à comprendre. L'original est ici.

C'est comme calculer petit à petit et construire. C'est assez rapide.

Je vais l'apporter là-bas.

Essayons cet algorithme en 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)

#résultat
3003079

Haskell utilise l'évaluation paresseuse, alors que faire avec Python?

Cependant, en tant qu'algorithme, il est seulement nécessaire de connaître le prochain nombre premier, j'ai donc conçu un itérateur séparément pour renvoyer une valeur et pour calculer un nombre premier en interne.

Au fait, c'est simple, mais si vous essayez Exécuter une fois et mesurer le temps avec l'argument 100000 sur IDLE

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

Environ 0,026 milliseconde.

Au début

>>> measure_t( first_prime_GE_sieve,100000)
16.222843885421753

Environ 16 secondes.

N'est-ce pas assez rapide?

Postscript

J'ai essayé de ne pas provoquer d'erreur d'exécution ci-dessus, mais est-ce généralement comme ça?

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

##résultat
2728129

Changé pour capturer et traiter StopIteration. Passez à l'itérateur s'il ne s'agit pas d'un tableau.

Ça a l'air bien. Mais cela semble un peu tard.

De même, si vous mesurez le temps d'exécution

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

0,034 millisecondes.