Prime factors

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

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

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.

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

• Integers
  • Zero
  • Units
  • Prime numbers
    • Primality
  • Composite numbers
    • Compositeness
    • Prime powers
    • Perfect powers

• Integer factorization
  • Divisibility
  • Divisibility triangle
  • Table of divisors (or table of factors)
  • Divisors (or factors)
  • Number of divisors (or number of factors)
  • Sum of divisors (or sum of factors)

• Prime factorization (or prime factorization (with multiplicity))
  • Prime factors (with multiplicity) (or prime divisors (with multiplicity)) (multiset of prime factors (with multiplicity))
  • Table of prime factors (with multiplicity)
  • Number of prime factors (with multiplicity)
    • Number of odd prime factors (with multiplicity)
  • Sum of prime factors (with multiplicity)
    • Sum of odd prime factors (with multiplicity)

• Distinct prime factorization
  • Distinct prime factors (or distinct prime divisors) (set of distinct prime factors)
  • Table of distinct prime factors
  • Number of distinct prime factors
    • Number of odd distinct prime factors
  • Sum of distinct prime factors
    • Sum of odd distinct prime factors

• Prime power factorization
• Coprime
• Coprimality
• Coprimality triangle
• Greatest common divisor
• Euclid's algorithm

External links

• Prime factors calculator using JavaScript (can handle numbers up to about 9 × 10¹⁵).
• Java applet: Factorization using the Elliptic Curve Method (finding factors with 20+ digits).