small medium large xlarge

• Use your span function and list comprehensions to return a list of the prime numbers from 2 to n.

A Possible Solution</summary>

```defmodule MyList do

def span(from, to) when from > to, do: []

def span(from, to), do: [ from | span(from+1, to) ]

def primes_up_to(n) do
range = span(2, n)
range -- (lc a inlist range, b inlist range, a <= b, a*b <= n, do: a*b)
end

end

IO.inspect MyList.primes_up_to(40) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
```

</details>

```defmodule Primes do
import MyList

def up_to(n) do
lc x inlist span(2, n), prime?(x), do: x
end

def prime?(2), do: true

def prime?(x) do
Enum.all?(span(2, x - 1), &(rem(x, &1) !== 0))
end
end

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] = Primes.up_to(40)
```

I didn’t figure this one out before looking here but had a similar approach to Hugo. Dave, the lc shorthand isn’t introduced in the book at this point so it would be helpful to have a note about that in your solution. Also, I think the difference operator (`--`) could be a great hint on the exercise.

Hugo’s solution could possibly be improved. One does not need to divide by all numbers less than n to determine if n is a prime. n only needs to be divided by all primes less than n but the primes would need to be accumulated somehow.

Not sure if this works. Simple test is sieve of Eratosthenes. You need to test each number n to see if it can be divided with numbers up to sqrt(n). If so it’s not a prime.

Something like this would work

``````defmodule MyList do
def len([]), do: 0
def len([_head | tail]), do: 1 + len(tail)
# _head does nothing, just placeholder here (_)
def generate_span(from, to) when from > to, do: []
def generate_span(from, to) when from <= to, do: [from | generate_span(from + 1, to)]
# span from to
def filter([], _func, remaining), do: remaining
def filter([item | items], func, remaining) do
if func.(item) do
filter(items, func, [item | remaining])
else
filter(items, func, remaining)
end
end
def filter(items, func), do: filter(items, func, [])
# filter the list according a value
def is_prime(number) do
if number > 2 do
len(filter(generate_span(2, Float.floor(:math.sqrt(number))), fn(n)-> if rem(number, n) == 0 do true else false end end))
else
0
end
end
# check if number is prime
def primes(_from, _to, [], primes), do: primes
def primes(from, to, [item | items], primes) do
if is_prime(item) == 0 do
primes(from, to, items, [item | primes])
else
primes(from, to, items, primes)
end
end
def primes(from, to) when from <= to, do: primes(from, to, generate_span(from, to), [])
# generate primes from to
end
``````

MyList.primes(1,10) # [7, 5, 3, 2, 1]

``````defmodule MyList do
def prime(a,b) when 1 < a and a < b do
for x <- span(a,b), _prime(x), do: x
end
def _prime(2), do: true
def _prime(a) when a > 2 do
!((for x <- span(2,a-1), do: rem(a,x) == 0) |> Enum.any?)
end
end

MyList.prime(2,10) # => [2,3,5,7]
``````

Is `lc` deprecated? I don’t see any reference to it on the main Elixir site, and `h lc` has nothing.

``````def primes_to(n) do
nums = span(2,n)
not_prime = for a <- nums, b <- span(2, div(a, 2)), rem(a, b) == 0, do: a
nums -- not_prime
end
``````

My ‘span’ function:

``````  def span(from, to) when from > to, do: []
def span(from, to), do: [from | span(from+1, to)]
``````

My ‘primes’ function:

``````  def primes(n) do
seive = span(2,n)
products = for x <- seive, y <- seive, x >= y, x*y <= n, do: x*y
seive -- products
end
``````

My solution is a little different to those here. It’s quite naive, but I think reads a lot simpler.

Also, my understanding is that list comprehensions use the `<-` syntax - a lot of the answers here don’t :/

```defmodule MyList do
def span(from, from), do: [from]
def span(from, to) when from < to do
[from | span(from+1, to)]
end

def primes(n) do
for num <- span(2, n), is_prime?(num), do: num
end

defp is_prime?(2), do: true
defp is_prime?(num) do
Enum.all?(span(2, num-1), &(rem(num, &1) != 0))
end
end
```

The solution I came up with is different than anything posted, so I thought I should share. It uses the sieve of eratosthenes to determine primes.

```defmodule Primes do
def upTo(n), do: _upTo(MyList.span(2, n))
defp _upTo([]), do: []
defp _upTo([x | primes]), do: [x | _upTo(for p <- primes, rem(p, x) != 0, do: p)]
end
```

EDIT: sqrt(n) optimization makes it much faster

```defmodule Primes do
def upTo(n), do: _upTo(MyList.span(2, n), :math.sqrt(n))
defp _upTo([x | primes], n) when x < n, do: [x | (for p <- primes, rem(p, x) != 0, do: p) |> _upTo(n)]
defp _upTo(primes, _n), do: primes
end
```

I came up with a faux sieve of E:

``````defmodule MyList do
def primes(bound) do
sieve(span(2, bound))
end

def sieve([]) do
[]
end

def sieve([ head | tail ]) do
[ head | sieve( for x <- tail, rem(x, head) > 0, do: x ) ]
end
end
``````

I like the simplicity of the implementation, but still want to figure out how to code a proper sieve with counting rather than remainder checking.

I found Rebecca’s solution the easiest to comprehend, as it used nothing not yet introduced in the book and it cleanly separated the prime check from the iteration code.

``````defmodule MyList do
require Integer
def primes(a) when a >= 2 do
for n <- 2..a, is_prime(n), do: n
end

def is_prime(2), do: true
def is_prime(n) when Integer.is_odd(n) do
for(x <- 3..round(:math.sqrt(n)),
Integer.is_odd(x),
do: x)
|> Enum.all?(&(rem(n, &1) != 0))
end
def is_prime(_), do: false
end
``````
``````  def getPrimes(n) do
for i <- span(2,n), isPrime(i), do: i
end
def isPrime(i) do
a=for j <- span(2,i-1),  rem(i,j)==0, do: i
List.first(a) == nil
end

``````

Do note that Dave Thomas’ answer as provided on 16 July 2013 is currently incorrect. It includes `lc` and `inlist` which have since been deprecated. Tim Morton was correct in wondering that in his answer above.

`lc` was replaced by `for`.

`inlist` was replaced by `<-`.

So Dave’s answer would look like the following with the updated syntax. Note: the `span` functions are correct and can remain unchanged.

``````  def primes_up_to(n) do
range = span(2, n)
range -- (for a <- range, b <- range, a <= b, a*b <= n, do: a*b)
end
``````

All together now.

``````defmodule MyList do

def span(from, to) when from > to, do: []

def span(from, to), do: [ from | span(from+1, to) ]

def primes_up_to(n) do
range = span(2, n)
range -- (for a <- range, b <- range, a <= b, a*b <= n, do: a*b)
end

end
``````

My solution for prime numbers (not efficient):

``````defmodule Awesome do
def prime(from, to) when is_number(from) and is_number(to) do
v = for
x <- Enum.into(from..to, []),
y <- _span(2, x - 1), rem(x, y) === 0 do
x
end
Enum.into(from..to, []) -- v
end

defp _span(from, to) when to >= from do
[from | _span(from + 1, to)]
end
defp _span(_from, _to), do: []

end
``````
``````defmodule MyList do
def span(from, to) when from > to, do: []
def span(from, to) do
[ from | span(from+1, to) ]
end

def primes_up_to(n) do
for i <- MyList.span(2,n), Math.is_prime?(i), do: i
end
end

defmodule Math do
def is_prime?(2), do: true
def is_prime?(n) do
!Enum.any?(2..round(:math.sqrt(n)), &(rem(n, &1) == 0))
end
end
``````

I tried to avoid creating a module and instead to just work with comprehensions. This is what I came up with (the `| x==2` is somewhat ugly):

``````nonprime = for x <- MyList.span(2,20), devisor <- MyList.span(2,x), devisor < x || x == 2, rem(x, devisor) == 0, do: x

MyList.span(2,20) -- nonprime
# -> should give: [3, 5, 7, 11, 13, 17, 19]
``````
``````defmodule Chapter10 do
alias Chapter7.Exercise5

def prime_up_to(n) do
for n <- Exercise5.span(8, n), _sieve_of_eratostenes(n),
into: [1, 2, 3, 5, 7],
do: n
end
defp _sieve_of_eratostenes(n) do
rem(n,2) != 0 && rem(n,3) != 0 && rem(n,5) != 0 && rem(n, 7) != 0
end
end
``````

My solution can be improved?, thanks

First, thanks Nikola for mentioning Sieve algorithm.

Here is my solution with techniques mentioned in this chapter.

``````defmodule Mylist do
def span(from,to) when from==to, do: [from]
def span(from,to) when from<to, do: [from|span(from+1,to)]
def span(from,to) when from>to, do: [from|span(from-1,to)]

def prime(up_to, _sieve) when up_to<4, do: span(1,up_to)
def prime(up_to, sieve), do: span(2,up_to) -- Enum.uniq(not_prime(up_to, sieve))
def not_prime(up_to, sieve) when sieve, do: for x <- span(4,up_to), y <- span(2,Float.floor(:math.sqrt(x))), rem(x,y) == 0, do: x
def not_prime(up_to, sieve) when sieve == false, do: for x <- span(4,up_to), y <- span(2,x-1), rem(x,y) == 0, do: x
end
``````

Here is example how to time two algorithms. True uses Sieve.

``````iex(20)> :timer.tc(fn -> length(MyList.prime(10_000,false)) end)
{3179937, 1229}
iex(21)> :timer.tc(fn -> length(MyList.prime(10_000,true)) end)
{240848, 1229}
iex(22)>
``````
``````@doc """
Sieve of Eratosthenes
"""
def prime_numbers(n) do
list = span(2, n)
for num <- list,
rem(num, 2) != 0 || num == 2,
rem(num, 3) != 0 || num == 3,
rem(num, 5) != 0 || num == 5,
rem(num, 7) != 0 || num == 7,
do: num
end
``````

This is the first working result I came up with. I ended up using only pattern matching and list recursion.

``````defmodule Chapter10 do
def span(from, to) when from > to, do: []
def span(from, to), do: [from | span(from + 1, to)]

def prime_number(n) when n < 2, do: []
def prime_number(n) do
for x <- span(2, n), prime_number_filter(x, span(2, x)), do: x
end

def prime_number_filter(n, [n]), do: true
def prime_number_filter(n, [h|t]) when n != h, do: rem(n, h) != 0 and prime_number_filter(n, t)
end
``````
```defmodule MyList do
def span(from, to) when from > to, do: []
def span(from, to), do: [ from | span(from + 1, to) ]

def is_prime(2), do: true
def is_prime(x) do
Enum.all?(span(2, x-1), &(rem(x, &1) !== 0))
end

def prime(n) do
for x <- span(2, n), is_prime(x), do: x
end
end
```

Here’s my solution. No recursion, only list comprehensions.

```defmodule MyList do
def primes(from, to) do
is_prime? = fn(number) ->
Enum.empty?(for div <- 2 .. number - 1, rem(number, div) == 0, do: div)
end
for number <- from .. to, is_prime?.(number), do: number
end
end

```

A bit wordy, but fast:

```defmodule MyList do
defp span(from, to) when from > to, do: []
defp span(from, to), do: [from|span(from+1, to)]

defp _is_prime(d,n) when d >= n, do: true
defp _is_prime(d,n) do
if rem(n, d) == 0 , do: false,
else: if d >= :math.sqrt(n), do: true,
else: _is_prime(d+1,n)
end

def is_prime(n) do
_is_prime(2, n)
end

def primes_to(h) do
for n <- span(2,h), is_prime(n), do: n
end
end
```

My solution does not have anything to do with list recursion and I had to look up `cond` in the following chapter of the book:

``````defmodule ExpandIfNotMultiple do

def of( [], x ), do: [x]

# 1st implementation
#  def of( list = [ head | _ ], x )
#  when rem( x, head ) == 0 do
#    list
#  end

#  def of( [ head | tail ], x ) do
#    [ head | of(tail, x) ]
#  end

# 2nd implementation
def of( list = [ head | tail ], x ) do
cond do
rem( x, head ) == 0 ->
list
# to speed it up a bit
List.flatten list, [x]
true ->
[ head | of(tail, x) ]
end
end

end

defmodule GiveMeFirstPrimes do

require Integer

def for(x) when x < 2, do: raise "try again with an integer greater than 1"

def for(2), do: [2]

def for(x), do: GiveMeFirstPrimes.for(x-1) |> ExpandIfNotMultiple.of(x)

end
``````

iex(55)> GiveMeFirstPrimes.for(40)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Using comprehensions and maps %{}

``````defmodule Primes do

def up_to(y) do
for n <- 2..y, is_prime?(n) == %{}, do: n
end

defp is_prime?(n) when (n != 2 and n != 3) do
for x <- 2..div(n,2), rem(n,x) == 0, into: %{}, do: {n,"not prime"}
end
defp is_prime?(n) when (n == 2 or n == 3) do
%{}
end

end
``````
You must be logged in to comment