In number theory, the prime factors of a positive integer are the prime numbers that divide into that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. In number theory, the prime factors of a positive integer are the prime numbers that divide into that integer exactly, without leaving a remainder. ... Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... Not to be confused with Natural number. ... In mathematics, a prime number (or a prime) is a natural number greater than 1 which has exactly two distinct natural number divisors: 1 and itself. ... Prime decomposition redirects here. ...

For a prime factor p of n, the multiplicity of p is the largest exponent a for which p^a divides n.

Two positive integers are coprime if and only if they have no prime factors in common. The integer 1 is coprime to every positive integer, including itself. This is because it has no prime factors; it is the empty product. It also follows from defining a and b as coprime if 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 a time that is polynomial in the number of digits involved. In mathematics, the integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ... ↔ ⇔ ≡ logical symbols representing iff. ... In mathematics, an empty product, or nullary product, is the result of multiplying no numbers. ... The Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. ...

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. Prime decomposition redirects here. ... In number theory, the fundamental theorem of arithmetic (or unique factorization theorem) states that every natural number either is itself a prime number, or can be written as a unique product of prime numbers. ...

For a positive integer n, the number of prime factors of n and the sum of the prime factors of n (not counting multiplicity) are examples of arithmetic functions of n that are additive but not completely additive. In number theory and computability theory, subfields of mathematics, a number-theoretic function is any function whose domain is the set of natural numbers. ... In number theory, an additive function is an arithmetic function f(n) of the positive integer n such that whenever a and b are coprime we have: f(ab) = f(a) + f(b). ...

Determining the prime factors of a number is an example of a problem frequently used to ensure cryptographic security in encryption systems; this problem is believed to require superpolynomial time in the length of the number - it is relatively easy to construct a problem that would take longer than the known age of the Universe to calculate on current computers. Encrypt redirects here. ... This box:      This article is about scientific estimates of the age of the universe. ...

Examples

• The prime factors of 6 are 2 and 3 (6 = 2 × 3). Both have multiplicity 1.
• 5 has only one prime factor: itself (5 is prime). It has multiplicity 1.
• 100 has two prime factors: 2 and 5 (100 = 2² × 5²). Both have multiplicity 2.
• 2, 4, 8, 16, etc. each have only one prime factor: 2. (2 is prime, 4 = 2², 8 = 2³, etc.)
• 1 has no prime factors. (1 is a unit)

See also

• Divisor
• Composite number
• Table of prime factors

In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... A composite number is a positive integer which has a positive divisor other than one or itself. ... This table contains the integer factorization for the numbers from 1 to 1002. ...

External links

• A Javascript Prime Factor Calculator. Can handle numbers up to about 9×10¹⁵
• Java applet: Factorization using the Elliptic Curve Method finding factors with 20+ digits
• Lists of composites with prime factorization (first 100, first 1000, first 10,000, first 100,000, and first 1,000,000).