# 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) – Mariano Suárez-Álvarez Jan 28 '13 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. – user7530 Jan 28 '13 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) {
int j, i, count=0;
int flag;

for(i = x; i <= y; i++) {
flag = 0;
for(j = 2; j <= i/2; j++) {
if(!(i%j)) {
flag = 1;
break;
}
if(!flag) count++;
}
}
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 – Amzoti Jan 30 '13 at 19:00
• there are better prime algorithms. – tanaydin May 8 '18 at 9:30
• This is actually the brute force approach. I think what we are looking for is an efficient algorithm. – Abrar Dec 14 '18 at 15:13

The simple answer is $\pi(y-1) - \pi(x+1)$, with $\pi(n)$ as the prime-counting function. There as no need for the Sieve of Eratosthenes as other answers have suggested, as efficient prime-counting functions exist, such as Lehmer's Formula.
{"ft_lang_label":"__label__en","ft_lang_prob":0.84047365,"math_prob":0.99987197,"size":3581,"snap":"2020-10-2020-16","text_gpt3_token_len":1069,"char_repetition_ratio":0.10930948,"word_repetition_ratio":0.023217248,"special_character_ratio":0.3166713,"punctuation_ratio":0.10990502,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999976,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-02-25T01:41:48Z\",\"WARC-Record-ID\":\"<urn:uuid:82de3b4d-b043-4202-b51e-88e6b229cd5d>\",\"Content-Length\":\"143765\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:bd6c8746-48fd-4187-a4eb-c7da3a418eb3>\",\"WARC-Concurrent-To\":\"<urn:uuid:a823ce91-2dd1-463e-acfd-9c1dcddebcba>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://math.stackexchange.com/questions/288747/how-to-find-number-of-prime-numbers-between-two-integers\",\"WARC-Payload-Digest\":\"sha1:QOCL7RJWYQJQFUGJE23FY2G2NAMMCZ4D\",\"WARC-Block-Digest\":\"sha1:NK4P3OCJIBJVUTKS2REESNWESRL6LMKZ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-10/CC-MAIN-2020-10_segments_1581875145989.45_warc_CC-MAIN-20200224224431-20200225014431-00235.warc.gz\"}"}