0Pricing
Competitive Programming Academy · Lesson

Prime Factorization & Divisors

Break N into prime powers and count divisors.

Break N Apart

Every integer above 1 is a unique product of primes. Finding that breakdown, its prime factorization, unlocks many number-theory problems. 🧩

The Trial Division Idea

Pull out the smallest prime that divides n, divide it away, and repeat. This simple trial division peels n down to 1.

All lessons in this course

  1. GCD, LCM & the Euclidean Algorithm
  2. Primality Testing up to sqrt(n)
  3. Sieve of Eratosthenes
  4. Prime Factorization & Divisors
← Back to Competitive Programming Academy