small medium large xlarge

Dave_gnome_head_isolated_pragsmall
16 Jul 2013, 02:25
Dave Thomas (389 posts)
  • 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>

Hugo-oculos-escuro_pragsmall
30 Dec 2013, 17:44
Hugo Baraúna (3 posts)
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)
Nathan-6kites_pragsmall
25 Sep 2014, 05:26
Nathan Feaver (9 posts)

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.

Scriptical_pragsmall
21 Oct 2014, 18:41
Nikola Pavlicevic (2 posts)

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.

Scriptical_pragsmall
21 Oct 2014, 19:51
Nikola Pavlicevic (2 posts)

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]

Generic-user-small
28 Dec 2014, 15:08
Pierre Sugar (57 posts)
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]
Generic-user-small
30 Dec 2014, 23:25
Tim Morton (2 posts)

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
Mva.2008.05_pragsmall
06 Mar 2015, 02:28
Manuel E Vidaurre Arenas (8 posts)

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
C2f77d9bcc71d1f9ddabd89a8ddf9615_pragsmall
17 May 2015, 14:58
Rebecca Skinner (6 posts)

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
387effdc9ab501aa1a2c36992208435d_pragsmall
22 May 2015, 19:57
Jason Desrosiers (1 post)

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
Generic-user-small
14 Jul 2015, 21:34
Aziz Harrington (1 post)

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.

Generic-user-small
27 Jul 2015, 20:12
Jim Kane (6 posts)

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.

4c5c2c297ed9f4664cfbe7733a011fb2_pragsmall
22 Aug 2015, 03:20
Artem Medeusheyev (8 posts)
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
Generic-user-small
25 Oct 2015, 03:40
Joel Regen (2 posts)
  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

Generic-user-small
26 Oct 2015, 14:15
Brett Wise (3 posts)

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
169065098_pragsmall
25 Dec 2015, 12:43
Bartosz Magryś (4 posts)

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
Generic-user-small
09 Apr 2016, 03:17
David Nelson (1 post)
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
Generic-user-small
06 May 2016, 11:41
Simon (2 posts)

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]  
Profilepicture_pragsmall
25 Jan 2017, 05:09
Romario López (7 posts)
defmodule Chapter10 do
  Code.load_file("chapter-7/chapter-7.exs")
  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

Generic-user-small
19 Jul 2016, 16:33
Karlo Smid (11 posts)

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)> 
Generic-user-small
11 Sep 2016, 07:08
Olga Grabek (3 posts)
@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
Generic-user-small
29 Sep 2016, 09:35
Bonghyun Kim (3 posts)

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  
Generic-user-small
04 Dec 2016, 09:13
Hailong Hao (10 posts)
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
Generic-user-small
28 Jan 2017, 01:05
Oleg (15 posts)

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

Generic-user-small
14 Mar 2017, 23:22
Pierre Jacomet (9 posts)

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
Generic-user-small
20 Apr 2017, 12:33
Zoltán Vincze (4 posts)

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
      :math.sqrt(x) < head ->
        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]

You must be logged in to comment