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)
Other articles related to "prime, prime factor":
... Kummer proved that if m and n are nonnegative integers and p is a prime number, then the largest power of p dividing equals pc, where c is the number of ... Equivalently, the exponent of a prime p in equals the number of nonnegative integers j such that the fractional part of k/pj is greater than the fractional part of n/pj ... Another fact An integer n ≥ 2 is prime if and only if all the intermediate binomial coefficients are divisible by n ...
... theory, the Golomb–Dickman constant appears in connection with the average size of the largest prime factor of an integer ... More precisely, where is the largest prime factor of k ... integer, then is the asymptotic average number of digits of the largest prime factor of k ...
Famous quotes containing the words factor and/or prime:
“In his very rejection of art Walt Whitman is an artist. He tried to produce a certain effect by certain means and he succeeded.... He stands apart, and the chief value of his work is in its prophecy, not in its performance. He has begun a prelude to larger themes. He is the herald to a new era. As a man he is the precursor of a fresh type. He is a factor in the heroic and spiritual evolution of the human being. If Poetry has passed him by, Philosophy will take note of him.”
—Oscar Wilde (1854–1900)
“By whatever means it is accomplished, the prime business of a play is to arouse the passions of its audience so that by the route of passion may be opened up new relationships between a man and men, and between men and Man. Drama is akin to the other inventions of man in that it ought to help us to know more, and not merely to spend our feelings.”
—Arthur Miller (b. 1915)