I am reading Cojocaru and Murty's Introduction to Sieve Methods and their Applications. They wait until Chapter 5 to discuss the Sieve of Eratosthenes for finding primes - and their version of it is not very algorithmic. She writes the inequality:
$$ \#\{ n \leq x : n \text{ not divisible by }p< z \} \approx x \prod_{p < z}\left( 1 - \frac{1}{p} \right) + O(...)$$
This makes sense the number of primes should be proportional to the residue classes which you left out upon sieving. The textbook spends a lot of time estimating the main $\prod_{p < z}\left( 1 - \frac{1}{p} \right)$ and the error term $O(...)$.
How do we turn this equation into an algorithm?
Knowing the sieve algorithm already I remember to keep the smallest prime, and we sieve accordingly.
The other example in that chapter focuses on twin primes. They given an approximation like so:
$$ \#\{ n \leq x : n \not \equiv 0,-2 \text{ for }p< z \} \approx x \prod_{p < z}\left( 1 - \frac{2}{p} \right) + O(...)$$
The book says, unfortunately, these are not the twin primes - I don't understand why. It says the number of twin primes is less than
$$ \#\{ \text{ primes }p < z \} + \#\{ n \leq x : n \not \equiv 0,-2 \text{ for }p< z \} = \pi(z)+ x \prod_{p < z}\left( 1 - \frac{2}{p} \right) $$
If this were an algorithm I take it to mean you still have to compute primes up to a certain point, but not all of the primes up to $x$ in order to find the twin primes.
The book is not very clear in many places, so I have put in my - possibly wrong - interpretation of the equations in certain spots. Maybe someone among you has the book or knows the Sieve of Eratoshenes very well.
My main complaint about the book is that it doesn't provide algorithms, just estimates.
