[GO] Prime number 2 in Python

Continuation of Prime numbers in Python and Prime numbers in Haskell 2. Iterators and generators were unclear, so I'll try a prime number generator.

This is the one I usually see.

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

(All results are the maximum number that can be calculated in paiza.io without time out. Not always the same, but as a measure of speed.)

I see. It feels like sifting an infinite length iterator while outputting a prime number. Well done.

Once you understand the contents, you will notice that it is the same as the comment code you received above. Only the difference between a function and an object.

Isn't it too fast?

How to do it in the Haskell area.

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
--result
[24684013]

It is transformed so that it is easy for you to understand. The original is here.

It feels like calculating little by little and building up. It's pretty fast.

I'll bring it over there.

Let's try this algorithm 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)
#result
3003079

Haskell uses lazy evaluation, so what to do with Python?

However, as an algorithm, it is only necessary to know the next prime number, so I devised an iterator separately for returning a value and for calculating a prime number internally.

By the way, it's simple, but if you try Run once and measure the time with argument 100000 on IDLE

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

About 0.026 ms.

The one at the beginning

>>> measure_t( first_prime_GE_sieve,100000)
16.222843885421753

About 16 seconds.

Isn't it pretty fast?

Postscript

I tried to avoid the runtime error above, but is it usually like this?

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

Changed to catch and process StopIteration. Change to an iterator if it's not an array.

It looks neat. But it seems a little late.

Similarly, if you measure the execution time

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

0.034 ms.

Recommended Posts

Prime number 2 in Python
Infinite prime number generator in Python3
Prime numbers in Python
Project Euler # 7 "1000 1st prime number" in Python
[Python 3] Prime factorization in 14 lines
Prime number enumeration and primality test in Python
I made a prime number generation program in Python
I made a prime number generation program in Python 2
Number recognition in images with Python
Prime number generation program by Python
Prime number enumeration in one line
Study, number guessing game in Python
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Unittest in python
Epoch in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
N-Gram in Python
Programming in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
LINE-Bot [0] in Python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
nCr in Python.
format in python
PPAP in Python
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
Project Euler # 3 "Maximum Prime Factors" in Python
I searched for prime numbers in python
Project Euler # 17 "Number of Characters" in Python
A program that determines whether a number entered in Python is a prime number
Sorted list in Python
Daily AtCoder # 36 in Python
Clustering text in Python
Daily AtCoder # 2 in Python
Implement Enigma in python
Daily AtCoder # 32 in Python