Prime factor

For the Star Trek: Voyager episode, see Prime Factors (Star Trek: Voyager).

In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's geometric position. He saw a whole number as a line segment, which has a smallest line segment greater than 1 that can divide equally into it.

For a prime factor p of n, the multiplicity of p is the largest exponent a for which p^a divides n. The prime factorization of a positive integer is a list of the integer's prime factors, together with their multiplicity. The fundamental theorem of arithmetic says that every positive integer has a unique prime factorization.

To shorten prime factorization, numbers are often expressed in powers, so

$288 = 2 \times 2 \times 2 \times 2 \times 2 \times 3 \times 3 = 2^5 \times 3^2.$

For a positive integer n, the number of prime factors of n and the sum of the prime factors of n (not counting multiplicity) are examples of arithmetic functions of n that are additive but not completely additive.

Determining the prime factors of a number is an example of a problem frequently used to ensure cryptographic security in encryption systems; this problem is believed to require super-polynomial time in the number of digits — it is relatively easy to construct a problem that would take longer than the known age of the Universe to solve on current computers using current algorithms.

Two positive integers are coprime if and only if they have no prime factors in common. The integer 1 is coprime to every positive integer, including itself. This is because it has no prime factors; it is the empty product. It also follows from defining a and b as coprime if gcd(a,b)=1, so that gcd(1,b)=1 for any b>=1. Euclid's algorithm can be used to determine whether two integers are coprime without knowing their prime factors; the algorithm runs in a time that is polynomial in the number of digits involved.

The function ${\omega(n)}$ represents the number of distinct prime factors of n, while ${\Omega(n)}$ represents the total number of prime factors of n. If $n = \prod_{i=1}^{\omega(n)} p_i^{\alpha_i}$ , then $\Omega(n) = \sum_{i=1}^{\omega(n)} \alpha_i$ .

For example, $24=2^3 \times 3^1$ , so: $\omega(24)=2$ and $\Omega(24)=3+1=4$ .

ω(n) for n = 1, 2, 3, ... is 0, 1, 1, 1, 1, 2, 1, 1, 1, ... (sequence A001221 in OEIS)

Ω(n) for n = 1, 2, 3, ... is 0, 1, 1, 2, 1, 2, 1, 3, 2, ... (sequence A001222 in OEIS)

External links [edit]

v t e Divisibility-based sets of integers

Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic Arithmetic number

Factorization forms	Prime number Composite number Semiprime number Pronic number Sphenic number Square-free number Powerful number Perfect power Achilles number Smooth number Regular number Rough number Unusual number

Constrained divisor sums	Perfect number Almost perfect number Quasiperfect number Multiply perfect number Hemiperfect number Hyperperfect number Superperfect number Unitary perfect number Semiperfect number Practical number

With many divisors	Abundant number Primitive abundant number Highly abundant number Superabundant number Colossally abundant number Highly composite number Superior highly composite number Weird number

Aliquot sequence-related	Untouchable number Amicable number Sociable number Betrothed number

Other sets	Deficient number Friendly number Solitary number Sublime number Harmonic divisor number Frugal number Equidigital number Extravagant number

See also [edit]

External links [edit]