Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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 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. –  TheUknown May 20 at 1:38

2 Answers 2

up vote 9 down vote accepted

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

share|improve this answer
    
"Divisions take longer than unit time" -- depends on the model! What is the runtime of the Sieve in this model? –  Raphael May 20 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 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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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