Skip to content

Instantly share code, notes, and snippets.

@ewildgoose
Created July 10, 2014 18:33
Show Gist options
  • Save ewildgoose/bedcefdb467b24ad2345 to your computer and use it in GitHub Desktop.
Save ewildgoose/bedcefdb467b24ad2345 to your computer and use it in GitHub Desktop.
Trial Division Prime Generation in Elixir
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment