Prime Factorization and Divisors
- Every integer has a unique prime factorization β Fundamental Theorem of Arithmetic.
- Trial division: O(βn) per number β sufficient for n up to ~10^12.
- From factorization: divisor count = Ξ (exponent+1), totient = n Γ Ξ (1-1/p).
RSA's security depends on one fact: factoring the product of two large primes is computationally hard. The best known classical algorithm (General Number Field Sieve) runs in sub-exponential but super-polynomial time. A 2048-bit RSA modulus would take longer than the age of the universe to factor on current hardware.
For small numbers β up to ~10^12 β trial division works fine. For competitive programming β up to ~10^6 per query β the SPF sieve turns factorization from O(βn) per query to O(log n). Knowing which regime you're in and choosing the right tool is the practical skill.
Trial Division
Check divisibility by all primes up to βn. O(βn) per number.
def prime_factors(n: int) -> dict[int, int]: """Returns {prime: exponent} factorization.""" factors = {} d = 2 while d * d <= n: while n % d == 0: factors[d] = factors.get(d, 0) + 1 n //= d d += 1 if n > 1: factors[n] = factors.get(n, 0) + 1 return factors print(prime_factors(360)) # {2:3, 3:2, 5:1} print(prime_factors(1001)) # {7:1, 11:1, 13:1} print(prime_factors(97)) # {97:1} β prime
{7: 1, 11: 1, 13: 1}
{97: 1}
Number of Divisors and Sum of Divisors
From the factorization n = p1^a1 Γ p2^a2 Γ ... Γ pk^ak: - Number of divisors: Ο(n) = (a1+1)(a2+1)...(ak+1) - Sum of divisors: Ο(n) = Ξ (p^(a+1) - 1) / (p - 1) - Euler's totient: Ο(n) = n Γ Ξ (1 - 1/p) for each prime p dividing n
def num_divisors(n: int) -> int: factors = prime_factors(n) result = 1 for exp in factors.values(): result *= (exp + 1) return result def sum_divisors(n: int) -> int: factors = prime_factors(n) result = 1 for p, exp in factors.items(): result *= (p**(exp+1) - 1) // (p - 1) return result def euler_totient(n: int) -> int: factors = prime_factors(n) result = n for p in factors: result -= result // p return result print(num_divisors(360)) # 24 print(sum_divisors(360)) # 1170 print(euler_totient(36)) # 12
1170
12
Listing All Divisors
def all_divisors(n: int) -> list[int]: divisors = [] for i in range(1, int(n**0.5) + 1): if n % i == 0: divisors.append(i) if i != n // i: divisors.append(n // i) return sorted(divisors) print(all_divisors(36)) # [1,2,3,4,6,9,12,18,36] print(len(all_divisors(360))) # 24
24
SPF Sieve for Batch Factorization
When factorizing many numbers up to n, precompute the Smallest Prime Factor (SPF) sieve. Each factorization then takes O(log n) instead of O(βn).
π― Key Takeaways
- Every integer has a unique prime factorization β Fundamental Theorem of Arithmetic.
- Trial division: O(βn) per number β sufficient for n up to ~10^12.
- From factorization: divisor count = Ξ (exponent+1), totient = n Γ Ξ (1-1/p).
- SPF sieve enables O(log n) factorization after O(n log log n) preprocessing.
- RSA security depends on the hardness of factorizing large semiprimes (products of two large primes).
Interview Questions on This Topic
- QHow many divisors does 10^6 have? How do you compute this from its factorization?
- QWhat is Euler's totient function and how is it computed from prime factorization?
- QFor what values of n is Euler's totient equal to n-1?
- QHow does the SPF sieve speed up batch factorization?
Frequently Asked Questions
What is a perfect number?
A perfect number equals the sum of its proper divisors (divisors excluding itself). 6 = 1+2+3, 28 = 1+2+4+7+14. Equivalently, Ο(n) = 2n. All known perfect numbers are even and correspond to Mersenne primes.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.