Primfaktor

Primfaktor, in number theory, is a prime factor of a natural number. A prime factor is a factor that is itself a prime number. Every integer greater than 1 can be expressed as a product of prime factors, written uniquely as a prime factorization: n = p1^a1 × p2^a2 × ... × pk^ak, where the pi are distinct primes and the ai are positive integers.

For example, 60 equals 2^2 × 3 × 5, and 18 equals 2 × 3^2. The Fundamental Theorem of Arithmetic guarantees that this factorization is unique up to the order of the factors. The exponents indicate the multiplicity of each prime factor in the factorization.

To find the prime factors of a given number, one may use trial division by small primes, or generate a list of primes with the Sieve of Eratosthenes and divide successively. For large numbers, specialized algorithms from computational number theory are used.

Prime factorization has applications in arithmetic, such as simplifying fractions, computing greatest common divisors and least common multiples, and in fields such as cryptography, where the difficulty of factoring large numbers underpins some public-key systems.

Notes: The concept applies to integers greater than 1. The number 1 has no prime factors by definition. Negative integers have the same prime factors as their absolute value.