# How to find number of prime numbers between two integers

I have two integers, x and y so that x < y. How many prime numbers are there between x and y (exclusive). Is there a formula or algorithm to compute?

• Look up the so called Prime Number Theorem, which gives an estimation for the number of prime numbers smaller than a given number. You will not find (usable) exact formulas. (There is obviously an algorithm to compute the number you want —simply count how many numbers in the range are prime!; what you want is an efficient algorithm) Jan 28, 2013 at 7:50
• How big are $x$ and $y$? One simple approach is to sieve $[x,y]$. If $y$ is not too large, and you have to repeat the computation many times for different $y$, you might also consider precomputing a table of primes, and the counting is then trivial. Jan 28, 2013 at 8:35

Let $\pi(x) = \#\{p\leq x \mid p \mbox{ is prime}\}$ be the prime counting function. The Prime Number Theorem tells us that $$\pi(x) \sim \frac{x}{\log x}.$$ (That is $\lim_{x\to \infty} \frac{\pi(x)}{x/\log x}=1$.) So, roughly speaking, around a large $x$, the probability that an integer is a prime is $1/\log x$. Thus, naively, one may expect that the number of primes in an interval $(x,y]$, for large $x$ is about $(y-x)/\log x$, and in a heuristic formula, $$\pi(y)-\pi(x)\sim \frac{(y-x)}{\log x} = \frac{h}{\log x}. \qquad(*)$$ Here $h=y-x$ is the length of the interval. This heuristic makes senses only for $h$ which is much bigger than $\log x$.

From the Prime Number Theorem $(*)$ holds if $h\sim \lambda x$, where $\lambda>0$ is fixed. From Riemann Hypothesis $(*)$ holds for $h\sim x^{1/2+\epsilon}$ for any fixed $\epsilon>0$. (Because the RH gives the error term in the PNT.) There are unconditional results by Huxley and Heath-Brown showing $(*)$ for $h$ roughly being $x^{7/12}$.

If $h=\log x \frac{\log \log x \cdot \log\log\log\log x}{\log\log\log x}$, then $(*)$ fails for a sequence $x_n \to \infty$. To deal with small' intervals Selberg worked with almost all $x$. Namely he considered $(*)$ for all $x\in \mathbb{R}_{+}\smallsetminus S$, where $|S\cap (0,x]|=o(x)$. In this sense $(*)$ holds if $h/\log^2 x\to 0$ conditionally on RH and for $h=x^{19/77+\epsilon}$ unconditionally.

There are also works on the case $h\sim\lambda \log x$. There the distribution of the number of primes on intervals of this size is Poission with parameter $\lambda$, conditionally on the Hardy-Littlewood prime tuple conjecture. I think this is due to Gallagher.

Finding the number of prime numbers between two given numbers $$x$$ and $$y$$ such that $$x$$ < $$y$$

int count_primes_between(int x, int y) {
//i is used to loop all numbers from x to y
//j is used to iterate over each number in the range specified by x and y
//count stores the number of primes
int j, i, count=0;
int f = 0;
//f stores number of factors of each number

for(i = x; i <= y; i++) {
for(j = 1; j <= i; j++) {
//if there is a factor other than 1 and n break out and increment
//count
if(!(i%j)) {
f++;
}
if(f == 2) count++;//prime nos has 2 factors
}
}
return count;
}

• Welcome to MSE! This is very difficult to read and understand. Can you update to add comments on how the algorithm works for this code snippet? Regards Jan 30, 2013 at 19:00
• there are better prime algorithms. May 8, 2018 at 9:30
• This is actually the brute force approach. I think what we are looking for is an efficient algorithm. Dec 14, 2018 at 15:13

The simple answer is $$\pi(y-1) - \pi(x)$$, with $$\pi(n)$$ as the prime-counting function. For large bounds, there is no need for the Sieve of Eratosthenes as other answers have suggested as efficient prime-counting functions exist, such as Lehmer's Formula.

• Hi qwr, sorry to bring up such an old post, but your answer has left me curious. I've never seen such a simple formula for counting primes. I'm pretty sure I'm blatantly displaying my ignorance here, but what is n / the prime-counting function` in the formula you provide? I checked en.wikipedia.org/wiki/Prime-counting_function and a couple other places, but I'm out of practice/need to brush up on basic math terminology, tbh. If you don't mind helping a layman out.. Jun 29, 2020 at 23:05
• Prime-counting function is usually implemented as en.wikipedia.org/wiki/Meissel%E2%80%93Lehmer_algorithm. It is a modification of a simple dynamic programming approach given by Meissel. The Wikipedia page on prime-counting function is pretty good. If you have more questions then please ask a new question.
– qwr
Jun 30, 2020 at 3:57