In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's geometric position. He saw a whole number as a line segment, which has a smallest line segment greater than 1 that can divide equally into it.
For a prime factor p of n, the multiplicity of p is the largest exponent a for which pa 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.
To shorten prime factorization, numbers are often expressed in powers, so
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.
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 super-polynomial time in the number of digits — it is relatively easy to construct a problem that would take longer than the known age of the Universe to solve on current computers using current algorithms.
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.
The function represents the number of distinct prime factors of n, while represents the total number of prime factors. If, then .
For example, so: and .
ω(n) for n = 1, 2, 3, ... is 0, 1, 1, 1, 1, 2, 1, 1, 1, ... (sequence A001221 in OEIS)
Ω(n) for n = 1, 2, 3, ... is 0, 1, 1, 2, 1, 2, 1, 3, 2, ... (sequence A001222 in OEIS)
Famous quotes containing the words prime and/or factor:
“The prime lesson the social sciences can learn from the natural sciences is just this: that it is necessary to press on to find the positive conditions under which desired events take place, and that these can be just as scientifically investigated as can instances of negative correlation. This problem is beyond relativity.”
—Ruth Benedict (1887–1948)
“Children of the middle years do not do their learning unaffected by attendant feelings of interest, boredom, success, failure, chagrin, joy, humiliation, pleasure, distress and delight. They are whole children responding in a total way, and what they feel is a constant factor that can be constructive or destructive in any learning situation.”
—Dorothy H. Cohen (20th century)