Erathosthenes' Sieve

From Omath

It's easy to implement Eratosthenes' Sieve in omath. Here's a sample implementation

sieve[n_]:=sieve[{},Range[2,n]]
sieve[n_,m_]:=Cases[sieve[m],_?(# >= n&)]
sieve[primes_List,{}]:=primes
sieve[primes_List,tail_List]:=sieve[Append[primes, tail[[1]]], DeleteCases[tail, _?(Mod[#,tail[[1]]] == 0&)]]
sieve[50]
sieve[1000,1050]

How does it work? We construct two lists; initially the first one is empty, the second one contains all the integers from 2 to n. The first list will contain the primes -- we build it be recursively appending the first element of the second list to the first, then striking out every multiple of this number appearing in the second list. Finally, when the second list is empty, we return all the primes!