Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
7  
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-Alvarez 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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

finding the number of prime numbers between two given numbers x and y such that x

int count_primes_between(int x,int y){  
int j,i,count=0,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;

}

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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