—
—
—
—
—
—
0
—
—
—
—
—
—
—
0
—
The Prime Factorization Calculator decomposes any positive integer into its unique product of prime factors. According to the Fundamental Theorem of Arithmetic, every integer greater than 1 can be expressed as a product of primes in exactly one way (up to the order of factors). For example, $$360 = 2^3 \times 3^2 \times 5^1$$.
This calculator performs systematic trial division by the primes 2, 3, 5, 7, 11, and 13, counting how many times each divides the input. It handles numbers up to 10,000 effectively. The tool reports the power (exponent) of each prime factor and any remaining factor greater than 13 that could not be further decomposed. For most numbers in range, the factorization will be complete since $$13^2 = 169$$ and numbers up to $$169^2 = 28,561$$ with no factor ≤ 13 must themselves be prime.
Prime factorization is essential for computing GCD and LCM, simplifying fractions, solving Diophantine equations, understanding modular arithmetic, and forms the mathematical foundation of public-key cryptography.
The algorithm performs sequential trial division:
Step 1 — Divide by 2: Repeatedly check if the current value is divisible by 2. Each successful division increments the power count and updates the quotient. Continue up to 10 divisions (handles up to $$2^{10} = 1024$$).
Step 2 — Divide by 3: Apply the same process with divisor 3, up to 6 divisions (handles $$3^6 = 729$$).
Steps 3-6: Repeat for primes 5, 7, 11, and 13 with decreasing maximum division counts since higher primes contribute fewer factors in the range.
The remainder after all divisions represents any prime factor larger than 13. If the remainder is 1, factorization is complete. If greater than 1, it is itself a prime (for inputs up to ~169²). The total prime factor count includes multiplicity: $$360 = 2^3 \times 3^2 \times 5$$ has $$3 + 2 + 1 = 6$$ total factors.
Each output row shows how many times that prime appears in the factorization. A count of 0 means that prime is not a factor. To reconstruct the number: $$n = 2^{f_2} \times 3^{f_3} \times 5^{f_5} \times 7^{f_7} \times 11^{f_{11}} \times 13^{f_{13}} \times \text{remainder}$$. The Remaining Factor shows 0 if factorization is complete, or a prime larger than 13 if one exists. The Total Prime Factors counts with multiplicity, useful for understanding the number's divisor structure.
Inputs
Results
360 = 2³ × 3² × 5¹. Six prime factors total (with multiplicity). Fully factored — no remainder.
Inputs
Results
2310 = 2 × 3 × 5 × 7 × 11 — the product of the first five primes (a primorial).
The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either prime or can be expressed as a unique product of prime numbers (up to ordering). For example, 84 is always $$2^2 \times 3 \times 7$$ — no other set of primes multiplies to 84. This uniqueness is why 1 is excluded from being prime.
Given factorizations of two numbers, the GCD takes the minimum power of each common prime, and the LCM takes the maximum. For example, 12 = 2² × 3 and 18 = 2 × 3². GCD = 2¹ × 3¹ = 6, LCM = 2² × 3² = 36. This method is elegant but slower than the Euclidean algorithm for large numbers.
After dividing by primes 2 through 13, any leftover quotient greater than 1 is shown as the remaining factor. For numbers up to about 28,000, this remainder will itself be prime (since it has no factor ≤ 13, and 13² = 169). For very large numbers, the remainder could be composite with large prime factors.
RSA encryption relies on the difficulty of factoring the product of two large primes. While multiplying two 300-digit primes takes milliseconds, no known classical algorithm can factor their product in a reasonable time. Quantum computers running Shor's algorithm could theoretically break RSA, which is driving research into post-quantum cryptography.
A number is square-free if no prime factor appears more than once (all exponents are 0 or 1). For example, 30 = 2 × 3 × 5 is square-free, but 12 = 2² × 3 is not (since 2 appears twice). Approximately 60.8% of all positive integers are square-free (the exact proportion is $$6/\pi^2$$).
If $$n = p_1^{a_1} \times p_2^{a_2} \times \cdots$$, the total number of divisors is $$(a_1 + 1)(a_2 + 1) \cdots$$. For 360 = 2³ × 3² × 5¹, divisor count = (3+1)(2+1)(1+1) = 24 divisors. This formula counts all positive divisors including 1 and n itself.
Roboculator Team
The Roboculator Team explains calculations, planning tools, and practical formulas in clear language for real-life situations.
How helpful was this calculator?
Be the first to rate!
