Skip to content

Instantly share code, notes, and snippets.

@hamidreza-s
Last active June 23, 2023 19:42
Show Gist options
  • Save hamidreza-s/9e3ed289f65759048875 to your computer and use it in GitHub Desktop.
Save hamidreza-s/9e3ed289f65759048875 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes algorithm for finding all prime numbers up to N written in Erlang.
-module(calc).
-export([prime_numbers/1]).
% Source: https://wbear.wordpress.com/2011/12/08/prime-numbers-with-erlang/
% Sieve of Eratosthenes algorithm for finding all prime numbers up to N.
% http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
% Generate list of prime numbers up to N.
prime_numbers(N) when is_number(N) ->
prime_numbers(N, generate(N)).
prime_numbers(Max, [H|T]) when H * H =< Max ->
[H | prime_numbers(Max, [R || R <- T, (R rem H) > 0])];
prime_numbers(_, T) -> T.
% Generate sequence 2..N
generate(N) -> generate(N, 2).
generate(Max, Max) -> [Max];
generate(Max, X) -> [X | generate(Max, X + 1)].
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment