# What is the name of this prime number algorithm?

Does the following recursive algorithm have a name? If so, what is it?

procedure main():
myFilter = new Filter( myPrime = 2 ) //first prime number
print 2 //since it would not otherwise be printed
for each n in 3 to MAX:
if myFilter.isPrime(n):
print n

object Filter:
integer myPrime
PrimeFilter nextFilter = NULL

procedure isPrime(integer n):
if n is multiple of myPrime:
return FALSE
else if nextFilter is not NULL:
return nextFilter.isPrime(n)
else
nextFilter = new PrimeFilter(myPrime = n)
return TRUE


Sample implementation in Java here

This is similar to the Sieve of Eratosthenes though after some discussion in the CS chat, we decided that it is subtly different.

• suggest a better question is reference-request to see where its been studied.... also its efficiency depends some on the implementation of the filter function... – vzn May 20 '14 at 0:59
• I agree with Yuval Filmus, your algorithm doesnt seem efficient than the original. If you are trying to improve the algorithm, you might want to check this paper : Two fast parallel prime number sieves Their algorithm is much more efficient with the use of wheel of factorization. Although, it may not be theoretically work optimal but can be work optimal given specific computer architectures. – Polynomial Proton May 20 '14 at 1:38

## 2 Answers

O'Neil  call this the "unfaithful sieve". It's much slower than the sieve of Eratosthenes.

For each prime $p$ you do work $\sim p/\log p$ and so the total number of divisions up to $x$ is roughly $x^2/(2\log^2 x)$ if you assume composites are free. (That's essentially true: they take at most $2\sqrt x/\log x$ divisions each for a total of at most $2x^{3/2}/\log x$ divisions.)

Divisions take longer than unit time, so the total bit complexity is about $O(x^2\log\log x/\log x)$.

 Melissa E. O’Neill, The Genuine Sieve of Eratosthenes

• "Divisions take longer than unit time" -- depends on the model! What is the runtime of the Sieve in this model? – Raphael May 20 '14 at 7:23
• @Raphael: I use two models, one in which divisions have unit cost (giving $O(x^2/\log^2 x)$) and one with input/output tape Turing machines with fast arithmetic subroutines (FFT mult/div) which gives $O(x^2\log\log x/\log x)$. The latter makes my answer comparable to Filmus' second answer. – Charles May 20 '14 at 14:52

Let me rephrase your algorithm (starting at a different base case):

Initialize P to be the empty list.
for n from 2 to MAX:
if no integer in P divides n:
add n to P
return P


Let $p_1,p_2,\ldots$ be an enumeration of the primes. The probability that $p_1,\ldots,p_i$ do not divide a number $n$ is roughly $$\prod_{j=1}^i \left(1 - \frac{1}{p_j}\right) \approx e^{-\sum_{j=1}^i p_j} \approx e^{-\sum_{j=1}^i j\log j} \approx e^{-\frac{1}{2} i^2 \log i}.$$ Therefore the inner loop runs for roughly this many iterations: $$\sum_{i=1}^\infty e^{-\frac{1}{2} i^2\log i} = O(1).$$ In total, the complexity is $O(n)$ divisions. In contrast, the Eratosthenes sieve requires $O(n\log\log n)$ additions.

For a fair comparison, we also need to factor it the computational complexity of operations on large numbers. Assuming that division can be done in time $O(m\log m)$ (which is the conjectured running time), where in our case $m = \log n$, your algorithm has bit complexity $O(n\log n\log\log n)$, matching the bit complexity of the sieve. However, the best known division algorithms are somewhat slower, both asymptotically and in practice, and so I expect your algorithm to be somewhat slower than the sieve.

Atkin's sieve uses only $O(n/\log\log n)$ additions and so is faster than both your algorithm and the Eratosthenes sieve. It also uses only $\tilde{O}(\sqrt{n})$ memory, compared to your $\sum_{p_i \leq n} \log p_i \approx \sum_{m=1}^{n/\log n} \log(m\log m) = \Theta(n)$, also shared by the Eratosthenes sieve.

• I get a very different analysis, see my answer. – Charles May 20 '14 at 4:00
• @Sukotto: No problem. If I had remembered the reference sooner I could have just copied it, though. :) – Charles May 21 '14 at 13:49
• Just in case someone wants to rush out and use the Sieve of Atkin, first read GordonBGood's post on the subject. "is faster" should be read as "asymptotically faster if one ignores all actual implementation details." – DanaJ May 25 '14 at 2:43
• @DanaJ: Agreed. I do expect that Atkin would win out eventually, but that would surely be for ranges $\gg10^{20}.$ – Charles Jun 15 '14 at 3:40