14
$\begingroup$

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?

$\endgroup$
2
  • 9
    $\begingroup$ 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) $\endgroup$ Jan 28 '13 at 7:50
  • $\begingroup$ 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. $\endgroup$
    – user7530
    Jan 28 '13 at 8:35
15
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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;
}
$\endgroup$
3
  • 3
    $\begingroup$ 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 $\endgroup$
    – Amzoti
    Jan 30 '13 at 19:00
  • 1
    $\begingroup$ there are better prime algorithms. $\endgroup$
    – tanaydin
    May 8 '18 at 9:30
  • 2
    $\begingroup$ This is actually the brute force approach. I think what we are looking for is an efficient algorithm. $\endgroup$
    – Abrar
    Dec 14 '18 at 15:13
-1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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.. $\endgroup$
    – TCooper
    Jun 29 '20 at 23:05
  • $\begingroup$ 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. $\endgroup$
    – qwr
    Jun 30 '20 at 3:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.