### Primes by double recursion

Posted on April 4, 2015

The idea is taken from here. Does it have to be this mind-bending?

``````class Primes
def initialize
@primes = {}
end

def is_prime(n)
if @primes.has_key?(n)
@primes[n]
else
@primes.store(n,
n > 1 &&
primes.take_while { |x| x <= Math.sqrt(n) }
.all? { |x| n % x != 0 })
end
end

def primes
[.lazy,
(3..Float::INFINITY).lazy
.select { |x| x % 2 != 0 && is_prime(x) }]
.lazy
.flat_map { |x| x }
end
end

p Primes.new.primes.take(10).force
#=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]``````

`flat_map { |x| x }` is the only known to me way to concatenate two lazy enumerators.

Having defined the lazy sequence of prime numbers I can easily find prime factors of a positive integer, but to avoid recursion it’s handy to define `uninject` method first:

``````def uninject(a)
xs = []
while xa = yield(a) do
x, a = xa
xs << x
end
xs
end

def prime_factors(n)
uninject([Primes.new.primes, n]) do |ps, a|
if a > 1
ps = ps.drop_while { |p| a % p != 0 }
[ps.first, [ps, a / ps.first]]
end
end
end

prime_factors(315) #=> [3, 3, 5, 7]``````