Primifaktoreerimise

Primifaktoreerimine, also known as prime factorization, is the process of decomposing a composite number into a product of its prime factors. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, the prime numbers are 2, 3, 5, 7, 11, and so on.

Every integer greater than 1 can be uniquely represented as a product of prime numbers, up to the order of the factors. This fundamental principle is known as the Fundamental Theorem of Arithmetic.

To perform primifaktoreerimine, one typically starts by dividing the number by the smallest prime number that divides it evenly. This process is then repeated with the resulting quotient until the quotient itself is a prime number. For instance, to find the primifaktoreerimine of 12, we can start by dividing by 2, which gives 6. Then, we divide 6 by 2 again, resulting in 3. Since 3 is a prime number, we stop. Therefore, the primifaktoreerimine of 12 is 2 × 2 × 3, or 2² × 3.

Primifaktoreerimine has numerous applications in number theory and computer science, including finding the greatest common divisor (GCD) and least common multiple (LCM) of two or more numbers, simplifying fractions, and in cryptography. The difficulty of performing primifaktoreerimine for very large numbers is the basis for the security of many modern encryption algorithms, such as RSA.