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/(2log^2 x)$ if you assume composites are free. (That’s essentially true: they take at most $2sqrt 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^2loglog 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
