<p>I am reading Cojocaru and Murty's <a href="http://rads.stackoverflow.com/amzn/click/0521612756" rel="nofollow">Introduction to Sieve Methods and their Applications</a>.  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:</p>

<p>$$ \#\{ n \leq x : n \text{ not divisible by }p&lt; z \} \approx 
x \prod_{p &lt; z}\left( 1 - \frac{1}{p} \right)  + O(...)$$</p>

<p>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 &lt; z}\left( 1 - \frac{1}{p} \right)$ and the error term $O(...)$.</p>

<p><strong>How do we turn this equation into an algorithm?</strong> </p>

<p><em>Knowing the sieve algorithm</em> already I remember to keep the smallest prime, and we sieve accordingly.</p>

<p>The other example in that chapter focuses on <em>twin primes</em>.   They given an approximation like so:</p>

<p>$$ \#\{ n \leq x : n \not \equiv 0,-2 \text{ for }p&lt; z \} \approx 
x \prod_{p &lt; z}\left( 1 - \frac{2}{p} \right)  + O(...)$$</p>

<p>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 </p>

<p>$$ \#\{ \text{ primes }p &lt; z \}
+ \#\{ n \leq x : n \not \equiv 0,-2 \text{ for }p&lt; z \} = \pi(z)+ x \prod_{p &lt; z}\left( 1 - \frac{2}{p} \right) $$</p>

<p>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.</p>

<hr>

<p>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.  </p>

<p>My main complaint about the book is that it doesn't provide algorithms, just estimates.</p>

CC BY-SA 3.0
2014-08-15T14:59:13.027Z
this all has been somewhat revolutionized by Zhang's recent results. nobody seems to have converted his findings into algorithms yet but presumably there are basic algorithms derivable from the new analysis.
vzn
CC BY-SA 3.0
2014-08-15T15:49:38.507Z
@vzn unrelated : what would be the uses of finding large twin primes, or finding them quickly?
john mangual
CC BY-SA 3.0
2014-08-15T16:15:56.747Z
are you asking for applications? a completely different question... fyi there are multiple such algorithms related to twin primes that one could imagine/ formulate, eg compute the _nth_ twin prime pair, find large pairs, etc... so maybe/ probably your question needs to be more specific to have an answer...
vzn
CC BY-SA 3.0
2014-08-15T16:18:46.273Z
@vzn my question is not about applications at the moment.  right now, just the relationship between the equation **counting** and the algorithm **enumerating** the twin primes, up to $x \in \mathbb{N}$.
john mangual
CC BY-SA 3.0
2014-08-16T11:12:54.500Z
In view of the last sentence of your question, I can’t help the feeling that you misunderstand what the term “sieve theory” means. It’s a subfield of number theory whose goal is to prove estimates, it has nothing to do with algorithms.
Emil Jeřábek
CC BY-SA 3.0
2014-08-16T11:46:25.747Z
@EmilJeřábek Then it's a one way street?  The algorithms can be used to derive estimates but not the other way around?  I think you are right that I misunderstood the intent of Cojocaru + Murty's book, but it can still make sense to ask is an algorithm exists.
john mangual
CC BY-SA 3.0
2014-08-16T11:56:41.963Z
You don’t derive the estimates from algorithms, it’s just two different things. As far as I can see, the only connection is the original sieve of Eratosthenes, which on the one hand can be considered an algorithm, and on the other hand inspired the sieve methods in number theory.
Emil Jeřábek
CC BY-SA 3.0
2014-08-16T12:08:17.337Z
Anyway, the algorithm suggested by your last equation is to first compute the list of all primes below $z$, output those that are twinned, take a second list containing numbers below $x$, and for each $p$ on the first list, sieve out all multiples of $p$ and their twins from the second list. The result will be accurate only if $z\ge\sqrt x$ or so, otherwise you’ll get a superset of twin primes. As far as I can see, it is computationally more efficient to just employ the usual sieve of Eratosthenes and weed out non-twin primes upon output.
Emil Jeřábek
CC BY-SA 3.0
2014-08-16T18:13:26.410Z
re the 1st boldface question. the sieve of Eratosthenes is a 2-millenia old algorithm. they seem to be using the general idea to compute estimates of prime densities (this in general also has a lot of connection to the Riemann hypothesis). that is a much _different_ aim than the original Eratosthenes sieve. so yes there are many tight connections between number theory & algorithms, incl primality theory, but maybe this particular book while worthwhile is not one to start with if you are focused on "algorithmic number theory"...
vzn
<nt.number-theory><comp-number-theory><asymptotics>
Sieve Methods for Twin Primes - How to extract algorithm from formula
john mangual
# Sieve Methods for Twin Primes - How to extract algorithm from formula

(Asked by: username_0 on 2014-08-15)

I am reading Cojocaru and Murty's [Introduction to Sieve Methods and their Applications](http://rads.stackoverflow.com/amzn/click/0521612756). 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.

**Tags:** nt.number-theory, comp-number-theory, asymptotics

> **Comments:**
> **username_1**: this all has been somewhat revolutionized by Zhang's recent results. nobody seems to have converted his findings into algorithms yet but presumably there are basic algorithms derivable from the new analysis.  
> **username_0**: @username_1 unrelated : what would be the uses of finding large twin primes, or finding them quickly?  
> **username_1**: are you asking for applications? a completely different question... fyi there are multiple such algorithms related to twin primes that one could imagine/ formulate, eg compute the _nth_ twin prime pair, find large pairs, etc... so maybe/ probably your question needs to be more specific to have an answer...  
> **username_0**: @username_1 my question is not about applications at the moment.  right now, just the relationship between the equation **counting** and the algorithm **enumerating** the twin primes, up to $x \in \mathbb{N}$.  
> **username_2**: In view of the last sentence of your question, I can’t help the feeling that you misunderstand what the term “sieve theory” means. It’s a subfield of number theory whose goal is to prove estimates, it has nothing to do with algorithms.  
> **username_0**: @EmilJeřábek Then it's a one way street?  The algorithms can be used to derive estimates but not the other way around?  I think you are right that I misunderstood the intent of Cojocaru + Murty's book, but it can still make sense to ask is an algorithm exists.  
> **username_2**: You don’t derive the estimates from algorithms, it’s just two different things. As far as I can see, the only connection is the original sieve of Eratosthenes, which on the one hand can be considered an algorithm, and on the other hand inspired the sieve methods in number theory.  
> **username_2**: Anyway, the algorithm suggested by your last equation is to first compute the list of all primes below $z$, output those that are twinned, take a second list containing numbers below $x$, and for each $p$ on the first list, sieve out all multiples of $p$ and their twins from the second list. The result will be accurate only if $z\ge\sqrt x$ or so, otherwise you’ll get a superset of twin primes. As far as I can see, it is computationally more efficient to just employ the usual sieve of Eratosthenes and weed out non-twin primes upon output.  
> **username_1**: re the 1st boldface question. the sieve of Eratosthenes is a 2-millenia old algorithm. they seem to be using the general idea to compute estimates of prime densities (this in general also has a lot of connection to the Riemann hypothesis). that is a much _different_ aim than the original Eratosthenes sieve. so yes there are many tight connections between number theory & algorithms, incl primality theory, but maybe this particular book while worthwhile is not one to start with if you are focused on "algorithmic number theory"...  

---

## 0 answers

