Sieve of Eratosthenes

Implementation of sieve of eratosthenes algorithm to calculate all the prime numbers until number given used as limit, using :atomics for O(1) access and concurrent marking.

How it works is:

• Create an :atomics array of size input + 1 where index = number (0 = prime, 1 = composite)
• Find small primes up to √input sequentially
• Mark all multiples of each small prime concurrently using Task.async (lock-free writes)
• Collect all indices still marked as prime

Installation

If available in Hex, the package can be installed by adding sieve_of_eratosthenes to your list of dependencies in mix.exs:

def deps do
  [
    {:sieve_of_eratosthenes, "~> 0.3.0"}
  ]
end

Usage

For calculate all the primes with a limit given you can call the module SieveOfEratosthenes.calculate_primes/1 like this.

iex> SieveOfEratosthenes.calculate_primes(1_000)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, ...]

Benchmarks

To run the benchmarks, just run mix run benchmarks/calculate_primes.ex and see the results on benchmarks/results/index.html

v0.3.0 (:atomics)

Rewritten using :atomics for O(1) access with concurrent marking. Enables 100M+ calculation.

v0.2.0 (Streams + Tasks)

v0.1.1

Maintainer

This project was developed by José Juan García in my track to become a elixir developer

Contributing

Feel free to recommend any change in favor of improving this project

Documentation can be generated with ExDoc and published on HexDocs. Once published, the docs can be found at https://hexdocs.pm/sieve_of_eratosthenes.