What is Prime Factorization?

Prime factorization is the unique decomposition of a composite number into a product of prime number factors.

What is the Fundamental Theorem of Arithmetic?

It states that every integer greater than 1 is either a prime number itself or can be represented uniquely as a product of prime powers.

How do you find the prime factors of a number?

Divide the number by the smallest prime factor (2, 3, 5...) repeatedly until the quotient becomes 1, recording each prime factor.

What is the difference between prime factors and composite factors?

Prime factors are prime numbers (e.g., 2, 3, 5). Composite factors are non-prime numbers that can be broken down further (e.g., 4, 6, 9).

How does prime factorization calculate GCD and LCM?

GCD uses the minimum exponent of shared prime factors. LCM uses the maximum exponent across all prime factors present in either number.

What is Euler Totient Function phi(n)?

Euler totient function counts the number of positive integers up to n that are relatively prime (coprime) to n, calculated using prime factors.

Why is prime factorization important in RSA Cryptography?

RSA security relies on the asymmetry that multiplying two large primes is fast, but factoring their 2048-bit product back into prime factors is computationally impossible for supercomputers.

What is Trial Division?

Trial division is a simple factorization method that tests potential prime divisors from 2 up to the square root of the target number.

What is Shor Algorithm?

Shor Algorithm is a quantum computing algorithm capable of factoring large integers in polynomial time, posing a theoretical threat to RSA encryption.

Why do hash tables use prime numbers for size?

Prime table sizes minimize hash key collisions by ensuring hash key strides are coprime to array length, spreading data evenly.

math calculator

Prime Factorization & Divisors Calculator

Decompose numbers into prime factors, find all divisors, and compute GCD/LCM with steps.

Formula Verified by Dr. Elena Rostova, PhD

Inputs

Integer to Factorize (≥ 2)

Results

Prime Status

360 is Composite

Number of Distinct Primes3

Total Divisors τ(n)24

Euler's Totient φ(n)96

Prime Factor Exponent Chart

Prime bases with exponent heights

Prime Factors

2exp = 3

3exp = 2

5exp = 1

Division Steps

Start with n = 360. Divide out each prime factor:

Step 1: \(8\) is divisible by \(2^{3}\). Divide: remaining = \(45\)

Step 2: \(72\) is divisible by \(3^{2}\). Divide: remaining = \(5\)

Step 3: Remaining factor is a prime: \(5\)

\[360 = 2^{3} \times 3^{2} \times 5\]

Total number of divisors: \(\tau(360) = (3+1) \times (2+1) \times (1+1) = 24\)

Euler\'s Totient: \(\phi(360) = 2^{3-1}(2-1) \times 3^{2-1}(3-1) \times 5^{1-1}(5-1) = 96\)

Formula

Prime Factorization Formula

n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}, \quad \tau(n) = \prod(a_i + 1)

Every integer ≥ 2 factors uniquely into primes. The number of divisors equals the product of each exponent incremented by one.

Step by step

How the calculation works

1Enter any integer ≥ 2. The calculator performs trial division to find all prime factors.
2The result shows the full prime factorization in exponential notation.
3See derived values including total divisors τ(n) and Euler's totient φ(n).

Related guides

Learn more about this calculation

Guide

Fraction Operations Guide: Add, Subtract, Multiply, Divide

Learn the rules for adding, subtracting, multiplying, and dividing fractions, with simplification steps and live DTC calculator workflows.

Site Guide

How to Use Do The Calculation Calculators: A Practical Step-by-Step Guide

Learn the fastest reliable workflow for using Do The Calculation calculators, reading results, checking formulas, and using save, print, share, and export actions correctly.

Fraction Calc

Fraction Calculator

Simplify and compute fractions using GCD from prime factorization.

Long Division

Long Division Calculator

Divide integers with step-by-step remainders.

math calculator

Prime Factorization & Divisors Calculator

Decompose numbers into prime factors, find all divisors, and compute GCD/LCM with steps.

Formula Verified by Dr. Elena Rostova, PhD

Inputs

Integer to Factorize (≥ 2)

Results

Prime Status

360 is Composite

Number of Distinct Primes3

Total Divisors τ(n)24

Euler's Totient φ(n)96

Prime Factor Exponent Chart

Prime bases with exponent heights

Prime Factors

2exp = 3

3exp = 2

5exp = 1

Division Steps

Start with n = 360. Divide out each prime factor:

Step 1: \(8\) is divisible by \(2^{3}\). Divide: remaining = \(45\)

Step 2: \(72\) is divisible by \(3^{2}\). Divide: remaining = \(5\)

Step 3: Remaining factor is a prime: \(5\)

\[360 = 2^{3} \times 3^{2} \times 5\]

Total number of divisors: \(\tau(360) = (3+1) \times (2+1) \times (1+1) = 24\)

Euler\'s Totient: \(\phi(360) = 2^{3-1}(2-1) \times 3^{2-1}(3-1) \times 5^{1-1}(5-1) = 96\)

Formula

Prime Factorization Formula

n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}, \quad \tau(n) = \prod(a_i + 1)

Every integer ≥ 2 factors uniquely into primes. The number of divisors equals the product of each exponent incremented by one.

Step by step

How the calculation works

1Enter any integer ≥ 2. The calculator performs trial division to find all prime factors.
2The result shows the full prime factorization in exponential notation.
3See derived values including total divisors τ(n) and Euler's totient φ(n).

Related guides

Learn more about this calculation

Guide