HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is the name of this prime number algorithm?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisthenumberwhatalgorithmnameprime

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#25914, answer score: 9

Revisions (0)

No revisions yet.