Trial Division Prime Generation in Elixir

gistfile1.ex

defmodule Euler.Math.Prime do

    def primes_up_to_slow(up_to) do
        wheel2357
        |> Stream.take_while( &( &1 <= up_to ) )
        |> Enum.reduce(
                [],
                fn(x, primes) ->
                    limit=Float.ceil(:math.sqrt(x))
                    if(Euler.Math.Prime.test_prime_fast?(x, limit, Enum.reverse(primes))) do
                        [x|primes]
                    else
                        primes
                    end
                end
        )
        |> Enum.concat([7,5,3,2])
        |> Enum.reverse
    end


    def primes_up_to_fast(up_to) do
        wheel2357
        |> Stream.take_while( &( &1 <= up_to ) )
        |> Enum.reduce(
                {[], {121, [11]}},
                fn(x, {primes, ptt = { test_valid_to, primes_to_test} }) ->
                    {test_valid_to, primes_to_test} = update_primes_to_test(x, ptt, primes)

                    if(Euler.Math.Prime.test_prime?(x, primes_to_test)) do
                        {[x|primes], {test_valid_to, primes_to_test}}
                    else
                        {primes, {test_valid_to, primes_to_test}}
                    end
                end
        )
        |> elem(0)
        |> Enum.concat([7,5,3,2])
        |> Enum.reverse
    end

    def primes_stream do
        primes =
        wheel2357
        |> Stream.transform(
                {[], {121, [11]}},
                fn(x, {primes, ptt = { test_valid_to, primes_to_test} }) ->
                    {test_valid_to, primes_to_test} = update_primes_to_test(x, ptt, primes)

                    if(Euler.Math.Prime.test_prime?(x, primes_to_test)) do
                        {[x], {[x|primes], {test_valid_to, primes_to_test}}}
                    else
                        {[], {primes, {test_valid_to, primes_to_test}}}
                    end
                end
            )

        Stream.concat([2,3,5,7], primes)
    end

    @doc "Test if relatively prime to a list of candidate primes"
    def test_prime?(n, primes) do
        test_up_to=Float.ceil(:math.sqrt(n))
        test_prime_fast?(n, test_up_to, primes)
    end

    def test_prime_fast?(_n, _ubound, []), do: true
    def test_prime_fast?(_n, ubound, [p|_]) when p > ubound, do: true

    def test_prime_fast?(n, _ubound, [p|_]) when rem(n,p) == 0, do: false
    def test_prime_fast?(n, ubound, [p|primes]) when rem(n,p) != 0 do
        test_prime_fast?(n, ubound, primes)
    end

    @doc "This version is about 2-3x slower. Why?"
    def test_prime_slow?(n, ubound, primes) do
        primes
        |> Stream.take_while( &( &1 <= ubound ) )
        |> Enum.all?( &( rem(n, &1) != 0 ) )
    end

    @doc "Wheel which excludes multiples of 2,3,5,7 from the input. Barely faster then 'odd_numbers'..?"
    def wheel2357 do
        wheel = Stream.cycle([2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10])
                |> Stream.transform( 11, fn(i, acc) -> {[acc], i+acc} end )
        # Stream.concat( [2,3,5,7], wheel )
    end

    def odd_numbers do
        Stream.iterate(3, &(&1+2) )
    end

    def update_primes_to_test(x, {test_valid_to, primes_to_test}, primes) do
        if(x > test_valid_to) do
            test_valid_to = List.first(primes)
            test_valid_to = test_valid_to * test_valid_to
            primes_to_test = Enum.reverse(primes)
        end
        {test_valid_to, primes_to_test}
    end


end