Straightforward implementation of Sieve Of Eratosthenes primes search algorithm in Elixir
This implementation uses some common optimizations:
- it works with the sequence of odd integers (because the only even prime number is 2)
- the multiples of each prime p generated directly by counting up from the square of the prime in increments of 2p (for odd primes)
Inspired by the Exercism task Nth Prime in Elixir
lib folder contains implementation of Sieve Of Eratosthenes primes search algorithm utilizing different data structures:
sieve_of_eratosthenes_array.exErlang array
This implementation creates an array of the size limit + 1 elements. Array index corresponds to a number we are checking, all elements with even indexes, besides 2, are preset to false. Then odd indexes processed sequentially starting from 3, the first odd prime, and for each index with true element in array its multiples (composite numbers) are marked as false. On the final step we get an indexes of the true elements of array as a list of prime numbers.
sieve_of_eratosthenes_ets.exErlang ETS
This implementation inserts the sequence of odd integers into ETS as list of K/V pairs: [{3, :prime}, {5, :prime}, {7, :prime}, {9, :prime} ...]. Then odd numbers processed sequentially starting from 3, the first odd prime, and for each prime its multiples (composite numbers) removed from the ETS. On the final step we form a list of all ETS keys and return them as a list of a prime numbers.
sieve_of_eratosthenes_map.exElixir Map
This implementation encodes the sequence of odd integers as Map: %{3 => :prime, 5 => :prime, 7 => :prime, 9 => :prime, ...}. Then odd numbers processed sequentially starting from 3, the first odd prime, and for each prime its multiples (composite numbers) removed from the Map. On the final step we get a list of all Map keys and return them as a sorted list of a prime numbers.
sieve_of_eratosthenes_mapset.exElixir MapSet
This implementation starts with a set containing 2 and all odd integers. Then odd numbers processed sequentially starting from 3, the first odd prime, and for each prime its multiples (composite numbers) removed from the set. On the final step we transform everything that left in a set into a sorted list of all prime numbers.
sieve_of_eratosthenes_list.exElixir List
This implementation starts with a list of odd numbers, iterating it element by element, moving primes from head to another list and deleting composite numbers from the list tail. The next iterations goes with the tail from the previous one.
Because List implementation is VERY SLOW it's excluded from the comparison with others
To get the list of the prime numbers up to the given Upper Limit use:
iex> Primes.SieveOfEratosthenes.Array.get_primes_list(10)
[2, 3, 5, 7]
iex> Primes.SieveOfEratosthenes.Map.get_primes_list(10)
[2, 3, 5, 7]
iex> Primes.SieveOfEratosthenes.MapSet.get_primes_list(10)
[2, 3, 5, 7]
You can compare different implementations of algorith by editing and executing try_me.exs:
mix run try_me.exs
test/test_data/ - contains files with lists of prime numbers from The Prime Pages
To run tests use standard command:
mix test
Slow tests (marked with a @slow tag) excluded by default. To run all test use following command:
mix test --include slow:true