Enter any number to find all its factors
The study of factors and divisibility dates back to ancient civilizations. Babylonian mathematicians created tables of reciprocals and worked with factor pairs for practical calculations in trade and astronomy. Ancient Egyptian scribes used factorization techniques for distributing goods and solving problems involving fractions, as documented in the Rhind Mathematical Papyrus from approximately 1550 BCE. Chinese mathematicians developed the concept of divisibility rules and used factorization for astronomical calculations during the Han Dynasty. [Wikipedia, History of Number Theory]
Euclid of Alexandria, often called the Father of Geometry, made foundational contributions to number theory in his work "Elements" around 300 BCE. Books VII and IX of the Elements contain the Euclidean Algorithm for finding the greatest common divisor, a method still used today. Euclid also informally established that every integer greater than 1 is either prime or can be expressed as a product of primes, though the complete Fundamental Theorem of Arithmetic would be formally proved much later by Gauss. Eratosthenes of Cyrene (circa 276 to 194 BCE) developed the Sieve of Eratosthenes, a simple and elegant algorithm for finding all prime numbers up to a given limit. [Wikipedia, Euclid] [Wikipedia, Eratosthenes]
Carl Friedrich Gauss, one of history's greatest mathematicians, formally proved and published the Fundamental Theorem of Arithmetic in his landmark work "Disquisitiones Arithmeticae" in 1801. The theorem states that every integer greater than 1 is either a prime number itself or can be represented as a unique product of prime numbers, regardless of the order of multiplication. This theorem provides the theoretical foundation for all factorization work and established prime numbers as the building blocks of all integers. Gauss's work revolutionized number theory and remains a cornerstone of modern mathematics. [Wikipedia, Fundamental Theorem of Arithmetic] [Wikipedia, Carl Friedrich Gauss]
The development of public key cryptography in the 1970s, particularly the RSA cryptosystem invented by Rivest, Shamir, and Adleman in 1977, created enormous practical interest in integer factorization. RSA security relies on the difficulty of factoring large semiprime numbers. This spurred the development of sophisticated factorization algorithms including the Quadratic Sieve by Carl Pomerance in 1981, the Lenstra Elliptic Curve Method invented in 1985 and published in 1987, and the General Number Field Sieve, which is the most efficient classical algorithm for the largest numbers today. The largest RSA number factored to date is RSA-250, a 250-digit number factored in February 2020 using approximately 2,700 CPU core-years. [Wikipedia, Integer Factorization] [Wikipedia, RSA]
A factor of a number is an integer that divides the number exactly without leaving a remainder. For example, the factors of 12 are 1, 2, 3, 4, 6, and 12 because each of these numbers divides 12 evenly. Factors always come in pairs: if a divides N, then N divided by a is also a factor. The only exception is when N is a perfect square, the square root pairs with itself. [Wikipedia, Divisor]
Understanding factorization requires distinguishing between prime and composite numbers. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Examples include 2, 3, 5, 7, 11, and 13. A composite number is a positive integer greater than 1 that has at least one divisor other than 1 and itself, meaning it can be factored into smaller integers. The number 1 is neither prime nor composite; it is called a unit. [Wikipedia, Prime Number]
Prime factorization is the process of breaking down a composite number into a product of prime numbers. For example, the prime factorization of 60 is 2 x 2 x 3 x 5, which is often written as 2 squared times 3 times 5. According to the Fundamental Theorem of Arithmetic, every composite number has a unique prime factorization. Prime factorization is used in many areas including simplifying fractions, finding greatest common divisors, least common multiples, and in cryptography. [Wikipedia, Prime Factor]
To find all factors of a number efficiently, mathematicians use the square root method. Since factors come in pairs where one factor is less than or equal to the square root and the other is greater than or equal to the square root, we only need to check divisibility up to the square root of the number. For each divisor found, we record both the divisor and its paired quotient. This approach reduces the computational work dramatically, especially for large numbers. For a number N, instead of checking all numbers up to N, we only need to check up to the square root of N. [Wikipedia, Divisor Finding]
Factorization has numerous practical applications across mathematics and computer science. In arithmetic, factors are used to simplify fractions and find common denominators. In algebra, factoring polynomials is essential for solving equations. In computer science, factorization is used in cryptography, particularly in the RSA encryption algorithm where security depends on the difficulty of factoring large numbers. Factorization is also used in error correcting codes, random number generation, and in the analysis of algorithm complexity. [Wikipedia, Factorization Applications]
Trial division is the simplest factorization algorithm, suitable for small numbers or educational purposes. The method tests each integer from 2 up to the square root of the number to see if it divides evenly. When a divisor is found, it is recorded along with its paired quotient. For prime numbers, trial division requires checking all numbers up to the square root. The algorithm's time complexity is O(square root of N), making it impractical for very large numbers but perfectly adequate for numbers up to several million. This Factor Finder tool uses an optimized version of trial division with the square root optimization, beginning from 1 rather than 2 in order to collect all factors including 1 and N itself. [Wikipedia, Trial Division]
Developed by the Greek mathematician Eratosthenes of Cyrene (circa 276 to 194 BCE), the Sieve of Eratosthenes is an elegant algorithm for finding all prime numbers up to a given limit. The method works by creating a list of numbers from 2 to the limit, then repeatedly marking multiples of each prime number starting from 2. After processing, the unmarked numbers are primes. This algorithm has time complexity O(n log log n) and is one of the most efficient ways to generate prime numbers. The sieve is often used as a preprocessing step for factorization when multiple numbers need to be factored. [Wikipedia, Sieve of Eratosthenes]
Named after Euclid of Alexandria from around 300 BCE, the Euclidean Algorithm finds the greatest common divisor (GCD) of two numbers. While not a direct factorization method, the GCD is closely related to factorization. The algorithm works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until the remainder becomes zero. The last nonzero remainder is the GCD. This algorithm is remarkably efficient with time complexity O(log min(a, b)) and remains in use today in cryptography and computer algebra systems. [Wikipedia, Euclidean Algorithm]
For factoring very large numbers, researchers have developed sophisticated algorithms. The Quadratic Sieve, invented by Carl Pomerance in 1981, is the fastest algorithm in practice for factoring numbers up to approximately 100 decimal digits. The General Number Field Sieve (GNFS), first described by John Pollard in 1988 and fully developed by Buhler, Lenstra, and Pomerance in 1993, is the most efficient classical algorithm for numbers larger than 100 digits. GNFS was used to factor RSA-250, a 250-digit (829-bit) semiprime, in February 2020 using approximately 2,700 CPU core-years of computation. These algorithms use advanced mathematical concepts including algebraic number theory, linear algebra over finite fields, and large scale distributed computing. [Wikipedia, Quadratic Sieve] [Wikipedia, General Number Field Sieve]
Invented by Hendrik Willem Lenstra Jr. in 1985 and formally published in the Annals of Mathematics in 1987, the Elliptic Curve Factorization Method (ECM) uses the theory of elliptic curves to find prime factors of composite numbers. ECM is particularly effective at finding small to medium-sized prime factors (roughly 10 to 50 digits) of large numbers, and is the best known algorithm when the size of the factor to be found is the dominant cost. The algorithm works by generating random elliptic curves over a finite field and performing scalar multiplication operations until a non-trivial factor is discovered. As of 2013, the largest prime factor found using ECM had 83 decimal digits. ECM is regularly used in combination with GNFS and other algorithms as a preprocessing step for factoring numbers of unknown structure. [Wikipedia, Lenstra Elliptic Curve Factorization]