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)
   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.

  • $\begingroup$ 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... $\endgroup$ – vzn May 20 '14 at 0:59
  • $\begingroup$ 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. $\endgroup$ – Polynomial Proton May 20 '14 at 1:38

O'Neil [1] 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)$.

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

  • $\begingroup$ "Divisions take longer than unit time" -- depends on the model! What is the runtime of the Sieve in this model? $\endgroup$ – Raphael May 20 '14 at 7:23
  • $\begingroup$ @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. $\endgroup$ – 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.

  • 1
    $\begingroup$ I get a very different analysis, see my answer. $\endgroup$ – Charles May 20 '14 at 4:00
  • $\begingroup$ @Sukotto: No problem. If I had remembered the reference sooner I could have just copied it, though. :) $\endgroup$ – Charles May 21 '14 at 13:49
  • 1
    $\begingroup$ 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." $\endgroup$ – DanaJ May 25 '14 at 2:43
  • 1
    $\begingroup$ @DanaJ: Agreed. I do expect that Atkin would win out eventually, but that would surely be for ranges $\gg10^{20}.$ $\endgroup$ – Charles Jun 15 '14 at 3:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.