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.
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?
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.
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?
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