This site is supported by donations to The OEIS Foundation.

Prime factors

From OeisWiki

(Redirected from Prime factor)
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
.

Contents

Canonical representation

The canonical representation of the unique prime factorization of
n
is
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
\Omega(n) = \sum_{i=1}^{\omega(n)} {\alpha_i}^1 = \sum_{i=1}^{\omega(n)} {\alpha_i}.\,

Sum of prime factors (with multiplicity)

Distinct prime factors

Number of distinct prime factors

The arithmetic function
ω (n)
represents the number of distinct prime factors of
n
\omega(n) = \sum_{i=1}^{\omega(n)} {\alpha_i}^0 = \sum_{i=1}^{\omega(n)} {1},\,

if you forgive the tautological expression.

Sum of distinct prime factors

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, ...}

See also





External links

Personal tools