### 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
[[2].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]
```