Fastest algorithm for finding the number of primes in a range
Using the Sieve of Eratosthenes this takes $O((M-N) + M^{1/2}) \log \log M)$. This will be the fastest unless M is quite large and / or N is quite close to M. 

If you had a case like $M = 10^{100}$, $N = 10^{100} - 10^{10}$ you would likely start with a sieve to throw out all of the 10 billion candidates that have a small divisor, leaving you with say $10^9$ candidates. Then you'd use Fermat's primality test to find all probable primes. Then you'd either say "that's good enough", or you follow it by a deterministic primality test for the remaining 43.4 million or so probable primes. 

If you do a deterministic primality test then you would run Fermat's test with fewer individual tests since you don't mind a few "probable primes" that are composite. If you don't do a deterministic primality test then you would run Fermat's test for a bit longer. In practice the question would be: What is the chance that there is a "probable prime" that is really composite, vs. what is the chance that a number is reported incorrectly as prime / non-prime because of a hardware problem.