Prime Number Checker

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. Composite numbers can be built by multiplying smaller integers. In this sense, primes are the atoms of multiplication: every integer greater than 1 has a unique prime factorization, apart from the order of the factors.

That uniqueness is the fundamental theorem of arithmetic. It is why primes matter far beyond recreational math. Fractions, divisibility, modular arithmetic, cryptography, and many algorithms rely on the fact that integers decompose into primes in one consistent way.

The simplest primality test tries dividing by possible factors. If no integer from 2 through the square root of n divides n, then n is prime. The square-root limit works because any factor larger than the square root would need a matching factor smaller than the square root.

For small and moderate numbers, trial division is easy to understand and reliable. For very large numbers, especially those used in cryptography, more sophisticated tests are needed. Some tests prove primality deterministically; others are probabilistic but can make the chance of error negligibly small.

Primes become less frequent as numbers grow, but they never stop. Euclid's classic proof shows that if you assume there are finitely many primes, multiplying them together and adding one produces a number not divisible by any prime in the assumed list. Therefore another prime must exist.

The prime number theorem describes their density: around a large number n, the chance of a random nearby integer being prime is roughly 1 / ln(n). This does not predict exactly where the next prime is, but it gives a remarkably good sense of how sparse primes become.

Prime numbers are central to public-key cryptography, hashing strategies, pseudorandom generation, and error-detecting structures. Some cryptographic systems depend on the fact that multiplying two large primes is easy, while factoring the product is hard with classical computers.

The mathematical idea is simple, but practical use is careful. Security requires prime generation with strong randomness, appropriate size, and resistance to implementation mistakes. Primality is a property of a number; trust depends on how that number was produced and used.