# Distribution of Prime Numbers

Prime numbers are interesting, not just in number theory, but also in computer science applications, in particular cryptography. One of the most interesting questions is, How are the prime numbers distributed? We actually know quite a bit about this but we're a long way from knowing everything. For example, we know how many we can expect to find in a given range, specifically the number of prime numbers less than or equal to *n* is asymptotically equal to $\frac{x}{\ln{x}}$. However, we can't answer questions like, "What's the millionth prime number?" or even, "What's the next prime number after a given one?"

The method that you're taught for finding the prime factorization of a number in middle school is very brute force: Divide the number by prime numbers, keeping the ones that work and discarding the ones that don't. An important question here, that relates to how primes are distributed, is, When can you stop checking? For example, if you want to find the prime factorization of 106926, do you really have to test every number between 2 and 106925 or can you stop sooner than that?

We're actually going to prove what the maximum value is in one of the upcoming lectures but, for this exploration, I want you to see if you can come up with a suggestion for the value experimentally. Start by taking the following numbers and making a list for each one of all the prime numbers that divide it. Once you've got your list, see if you can come up with a proposal for what the upper bound on the prime numbers that can divide another number must be.

18112256289