(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

- $n=\prod _{i=1}^{\omega (n)}{p_{i}}^{\alpha _{i}},\,$

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

super-polynomial 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

- $\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 represents the

number of distinct prime factors of

- $\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

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