What is the name of this prime number algorithm?

Problem Detail: 

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.

Asked By : Sukotto

Answered By : Charles

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25914