Wednesday, December 23, 2015

A couple of things..........................



What is the good way to find the number of prime numbers that are less than or equal to the given number?


The trouble with sieve methods (suggested by Rajat Khandelwal's answer to Mathematics: What is the good way to  find the number of prime numbers that are less than or equal to the given number?) is that they give you a lot more than you're asking for: they provide an actual list of those primes up to your bound, and you just want to know how many there are. For certain ranges of upper bounds, finding the actual primes is impractical, but you can still determine their number.

The number of primes up to x is traditionally called π(x). So you're looking for a way to determine π(x) given x. There are very easy ways to do so if you'd settle for anapproximation. Let's consider two well-known such approximations:

A) π(x)xlnx

B) π(x)Li(x)=x21lntdt

Both of those approximations are "good" in the sense that the ratio between the left side and the right side tends to 1 as x gets larger and larger. However, they are not equally good: B) is much better than A), however A) is slightly easier to remember and, with some preparation, you can use it in your head or with pencil and paper for some really large values of x.

Let's take an example. Suppose you want to know how many primes there are less than one trillion (that's 1012). To use method A), we need to know what ln(1012) is. Well, that's obviously 12 times ln(10), and ln(10) is a number you may want to memorize (an approximation for) if you care about prime counting. It's about 2.30. So 12 times this is about 27.6, and therefore the number of primes up to a trillion is about a trillion divided by 27. In other words: roughly 1 number out of 27 in this range is a prime. That's actually a pretty useful way to understand the answer - much more intuitive than the precise number of such primes (which, incidentally, is 37,607,912,018).

The error in this case is about 1 billion - method A) yields about 36 billion primes, while in fact there are 37 billion. That's not so bad relatively speaking, but still feels somewhat lame to lose about a billion primes. That's where approximation B) comes in. If you have a way to do this integral (there are numerous ways to do that - it's a topic for a whole other answer), you get 37,607,950,281, about 38,263 more than the actual number. This is a ridiculously good answer: it is off by about 0.0001%.



If you really insist on finding π(x) exactly, up to the hundreds and tens and ones, there are indeed ways of doing so so which are considerably more efficient than an entire sieve. The first such method was devised by Meissel in the 19th century and improved by Lehmer in the 20th; there's a very nice write up of it here: http://www.dtc.umn.edu/~odlyzko/.... This algorithm uses about O(x2/3) arithmetic operations and takes up about O(x1/3)space. A naive sieve method obviously requires O(x) space, so that's a huge improvement.

No comments:

Post a Comment