Prime number theorem

The prime number theorem (PNT) describes the approximate distribution of primes among the positive integers. As integers get larger, primes get rarer at a rate quantified by this theorem.

The prime-counting function $\pi(x)$, which returns the number of primes less than or equal to $x$, has the following asymptotic behavior: $$\lim_{{x \to \infty}} \pi(x) = \frac{x}{\ln(x)}$$ Therefore, for large $x$, the function $\frac{x}{\ln(x)}$ closely approximates $\pi(x).$

A graph of the prime-counting function.^[1]

This leads to a few useful applications. First of all, if you wanted to get an idea of roughly how many primes exist among the first $512$ positive integers, you'd just need to calculate $\frac{512}{\ln(512)} \approx 82.$

Furthermore, if you wanted to estimate the probability of selecting a prime out of the first $512$ positive integers, you'd just need to calculate $\frac{82}{512} \approx 0.16.$

Generally, the probability of selecting a prime out of the first $x$ positive integers can be estimated using the formula $\frac{1}{\ln(x)}.$

The prime number theorem is also useful for generating large primes because it gives you an estimate of how many times you'd need to randomly generate an integer in a specific range before you're likely to get one that passes a primality test. Without going into specifics, the number of random trials necessary depends on the number of digits of the prime you are trying to generate, rather than its magnitude, which is why this method of generating primes is efficient.

⚠ Why would you want to generate a large prime? Well, to give an example, prime-sized hash tables can benefit from minimized collisions and enhanced probing. So, if you need space for $n$ entries in your hash table, it's better to generate a prime number greater than or equal to $n$ and use that as the hash table's size, allowing you to enjoy the benefits of the unique mathematical properties of primes. (According to Euclid's theorem, you'll always be able to find a large enough prime!)

⚠ Also, it should be noted that the generation of large prime numbers is essential in cryptography.

Contents

References

PrimePi.svg: Bender2k14, CC BY-SA 3.0, via Wikimedia Commons.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort