// NUMBER THEORY · INTERMEDIATE

Prime Factorization

Every whole number is a unique fingerprint of prime building blocks. Learn to split, factor, and reconstruct numbers one prime at a time.

Start Factoring Build the Tree
Intermediate·18 min·Mathematics · Number Theory
Reviewed by CodeTikki Academic Team

Prerequisites: Prime numbers · Division · Exponents (optional)

// VISUALIZER

Split a number into its prime atoms

Trial division keeps dividing by the smallest possible prime until nothing is left. Enter a number and watch the factor tree grow.

Press PLAY to factor 84 step by step.

Prime factors found

None yet

Step

0 / 5

Current n

84

Factors Found

0

// MINI GAME

Factor Tree Builder

Click the prime buttons to divide the current number. Reach 1 before time runs out to build the tree and score big.

Growing the tree...

// FLOWCHART

Algorithm flow

// FLOWCHART · Prime Factorization
Trial division
NoYesNoYesStartRead nd = 2factors = []d × d > n?n mod d == 0?factors.push(d)n = n / dd = next primefactors.push(n)Output factorsEnd

Press PLAY to trace the algorithm through the flowchart.

0 / 12

// PSEUDOCODE

Trace the code

// PSEUDOCODE · Prime Factorization
Trial division for n = 84
n = 84
1function factorize(n):
2 factors = []
3 d = 2
4 while d * d <= n:
5 if n mod d == 0:
6 factors.push(d)
7 n = n / d
8 else:
9 d = d + 1
10 if n > 1:
11 factors.push(n)
12 return factors

Press PLAY to step through the algorithm line by line.

0 / 22

// TUTORIAL QUIZZES

Test your mastery

From factor trees to GCD/LCM from factors, prove you can break any number into its primes.

// PRACTICE & ASSESS

Test your understanding

Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.

💻

Coding Problems

The Factor Tree: Find All Prime FactorsL2The Divisor Counter: Count Divisors from FactorsL4The Smallest Multiple: LCM from FactorsL3The Shared Factors: GCD from Prime FactorsL3The Pollard Rho FactorizerL9

// REFERENCES

Sources & further reading

  1. [1]
    The Fundamental Theorem of ArithmeticEuclid — Book VII, Proposition 32 and Book IX, Proposition 14
  2. [2]
    Introduction to Algorithms (CLRS)T. H. Cormen et al. — Number-theoretic algorithms
  3. [3]
    Prime Numbers: A Computational PerspectiveRichard Crandall & Carl Pomerance
  4. [4]
    The Art of Computer Programming, Vol. 2Donald Knuth — Seminumerical Algorithms

// READY?

Solve systems of congruences

Next up: Chinese Remainder Theorem. Combine remainders from different moduli like a master cryptographer.

Chinese Remainder Theorem Sieve of Eratosthenes