patternMinor
What is the name of this prime number algorithm?
Viewed 0 times
thisthenumberwhatalgorithmnameprime
Problem
Does the following recursive algorithm have a name? If so, what is it?
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.
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 TRUESample 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
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.