# Erlang, Primes, and Sieves Again (Lazy edition)

I was working on the Project Euler problems, specifically problem 7, and decided to implement a prime number generator based of my previous prime number implementation based off the Melissa O'Neill paper. The problem says that, given that the 6th prime number is 13, find the 10,001st prime. Since we don't have a known upper bound to use the primes:queue/1 function, I created a lazy sieve that would return the next prime, its position, and an iterator. The code:

-export([lazy_sieve/0]). lazy_sieve() -> Table = insert_prime(2, skew_kv:empty()), [ { 2, 1 } | fun() -> lazy_sieve({ 3, 2 }, Table) end ]. lazy_sieve({ X, Pos }, Table) -> {NextComposite, _Value} = skew_kv:min(Table), case NextComposite =< X of true -> lazy_sieve({X+1, Pos}, adjust(Table, X)); _Else -> [ {X, Pos} | fun() -> lazy_sieve({X+1, Pos+1}, insert_prime(X,Table)) end] end.

This can be used thusly:

1>[{Prime1, Pos1} | Next1] = primes:lazy_sieve(). % Prime1 = 2, Pos1 = 1, Next1 = fun() 2>[{Prime2, Pos2} | Next2] = Next1(). % Prime2 = 3, Pos2 = 2, Next2 = fun() 3>[{Prime3, Pos3} | Next3] = Next2(). % Prime3 = 5, Pos3 = 3, Next3 = fun()

This makes defining a function to find the nth prime trivial:

-export([nth/1]). nth(N) -> nth(lazy_sieve(), N). nth([ {Prime, N} | _Next], N) -> Prime; nth([ {_Prime, _Pos} | Next], N) -> nth(Next(), N).

Lazy evaluation twice, in the main functionality and in the value of a
key in the queue. And the performance of nth is pretty good too (time is
the left number, in *mirco*-seconds, and the 10,000st prime is the right
number):

9> timer:tc(primes, nth, [10001]). {1635839,104743} % 1.6 seconds 10> timer:tc(primes, queue, [104743]). {1788997, % 1.7 seconds to generate the full list of primes [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73, 79,83,89,97,101,103|...]}

So it takes 1.6 seconds to find the 10,001st prime and 1.7 seconds to generate the list of primes up to the 10,001st prime.