primtal

Primtal, in several languages including Norwegian and Swedish, refers to a prime number. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. By contrast, composite numbers have more than two positive divisors. The number 2 is the smallest prime and the only even prime.

The fundamental theorem of arithmetic states that every integer greater than 1 either is prime or can be factored uniquely as a product of primes, up to the order of the factors. This gives primes their central role in number theory, as the building blocks of all integers.

There are infinitely many primes. Euclid’s proof considers a product of known primes plus one and shows that any finite list misses a prime, implying an unbounded supply of primes.

Primality testing and generation: Trial division is sufficient for small numbers. The Sieve of Eratosthenes efficiently finds all primes up to a limit. For large numbers, probabilistic tests such as Miller–Rabin, and deterministic variants for defined ranges, are common in practice and used in cryptographic applications.

Distribution: The prime number theorem shows that the number of primes not exceeding n is asymptotically n/log n, so primes become sparser as numbers grow, but there are infinitely many primes.

Applications: Primes are central in number theory and underpin modern cryptography, especially public-key systems such as RSA, which rely on the difficulty of factoring large numbers and on efficient primality testing.