From OeisWiki
(Redirected from
Prime factor)
There are no approved revisions of this page, so it may
not have been
reviewed.
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
units, for which a smaller line segment of length greater than or equal to
unit is used to measure exactly the line segment with length of
units, where line segments corresponding to prime numbers can be measured only with a smaller line segment of length
.
Canonical representation
The canonical representation of the
unique prime factorization of
is

where
is the
number of distinct prime factors of
and
is the
th prime factor, in ascending order, of
.
Prime factors (with multiplicity)
Factoring a number
is believed to require
superpolynomial time in its number of digits. For a prime factor
of
, the
multiplicity of
is the largest exponent
for which
divides
. 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 represents the
number of prime factors (with multiplicity) of

Sum of prime factors (with multiplicity)
Distinct prime factors
Number of distinct prime factors
The
arithmetic function represents the
number of distinct prime factors of

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
is coprime to every positive integer, including itself, since it has no prime factors (
empty product of primes.) It follows that
and
are coprime if and only if their
greatest common divisor is
, i.e.
, so that
for any
.
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
of
distinct prime factors of
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
of
prime factors (with multiplicity) of
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
, we get the
empty product, i.e.
) of
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
, we get the
empty product, i.e.
) of
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