This site is supported by donations to The OEIS Foundation.

# Prime factors

Jump to: navigation, search

This article needs more work.

Please help by expanding it!

In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called prime factorization.

A prime factor can be visualized by understanding Euclid’s geometric interpretation. He saw a whole number as a line segment with length of
 n
units, for which a smaller line segment of length greater than or equal to 1 unit is used to measure exactly the line segment with length of
 n
units, where line segments corresponding to prime numbers can be measured only with a smaller line segment of length 1.

## Canonical representation

The canonical representation of the unique prime factorization of
 n
is
${\displaystyle n=\prod _{i=1}^{\omega (n)}{p_{i}}^{\alpha _{i}},\,}$
where
 ω (n)
is the number of distinct prime factors of
 n
and
 pi
is the
 i
th prime factor, in ascending order, of
 n
.

## Prime factors (with multiplicity)

Factoring a number
 n
is believed to require super-polynomial time in its number of digits. For a prime factor
 pi
of
 n
, the multiplicity of
 pi
is the largest exponent
 αi
for which
 pi αi
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 up to order of factors.

### Number of prime factors (with multiplicity)

The arithmetic function
 Ω (n)
represents the number of prime factors (with multiplicity) of
 n
${\displaystyle \Omega (n)=\sum _{i=1}^{\omega (n)}{\alpha _{i}}^{1}=\sum _{i=1}^{\omega (n)}{\alpha _{i}}.\,}$

## Distinct prime factors

### Number of distinct prime factors

The arithmetic function
 ω (n)
represents the number of distinct prime factors of
 n
${\displaystyle \omega (n)=\sum _{i=1}^{\omega (n)}{\alpha _{i}}^{0}=\sum _{i=1}^{\omega (n)}{1},\,}$

if you forgive the tautological expression.

## Coprimality

Two positive integers are coprime if and only if they share no common prime factors. The integer 1 is coprime to every positive integer, including itself, since it has no prime factors (empty product of primes). It follows that
 a
and
 b
are coprime if and only if their greatest common divisor is 1, i.e.
 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 polynomial time in the number of digits involved.

## Sequences

The number
 ω (n)
of distinct prime factors of
 n, n   ≥   1,
are (see A001221 and number of prime factors (with multiplicity))
{0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 3, 1, 2, 2, 1, 2, 3, 1, 2, 2, 3, 1, 2, 1, 2, 2, 2, 2, 3, ...}
The number
 Ω (n)
of prime factors (with multiplicity) of
 n, n   ≥   1,
are (see A001222 and number of distinct prime factors)
{0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 3, 3, 1, 3, 1, 5, 2, 2, 2, 4, 1, 2, 2, 4, 1, 3, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 4, 1, 2, 3, 6, 2, 3, 1, 3, 2, 3, 1, 5, 1, 2, 3, 3, 2, 3, ...}
The smallest prime factor (for
 n = 1
, we get the empty product, i.e.
 1
) of
 n, n   ≥   1,
gives (A020639)
{1, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2, 31, 2, 3, 2, 5, 2, 37, 2, 3, 2, 41, 2, 43, 2, 3, 2, 47, 2, 7, 2, 3, 2, 53, 2, 5, 2, 3, 2, 59, 2, 61, 2, 3, 2, 5, 2, 67, 2, 3, 2, 71, ...}
The largest prime factor (for
 n = 1
, we get the empty product, i.e.
 1
) of
 n, n   ≥   1,
gives (A006530)
{1, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 3, 13, 7, 5, 2, 17, 3, 19, 5, 7, 11, 23, 3, 5, 13, 3, 7, 29, 5, 31, 2, 11, 17, 7, 3, 37, 19, 13, 5, 41, 7, 43, 11, 5, 23, 47, 3, 7, 5, 17, 13, 53, 3, 11, 7, 19, 29, 59, 5, 61, 31, 7, 2, 13, ...}