Math, number theory, and combinatorics · HTML
A sieve marks multiples of each newly found prime p; SPF[x] stores the smallest prime divisor and supports repeated division.
Recognition signals
- All primes in a bounded range are needed
- Many moderate integers need factorization
- Divisor counts or prime exponents determine the answer
- Trial division repeats work
- Coprimality or prime-factor sets matter
False friends
| Signal | Why it is different |
|---|
| One enormous integer | Sieving to its square root may be infeasible; use a large-integer method. |
| Only the GCD of two values | Euclid is direct and does not need full factors. |
Core invariant
After processing prime p, its in-range multiples are marked; in SPF, the first factor written is the smallest prime factor.
State, transition, and processing order
| Item | Definition |
|---|
| State | An is-prime or SPF array, current candidate p, and optionally a prime list. |
| Transition | An unmarked p is prime; mark from p². For factorization, repeatedly divide x by SPF[x]. |
| Frontier / order | Candidates increase, and all effects of prime factors below p have already propagated. |
Python skeleton
def smallest_prime_factors(n):
spf = list(range(n+1))
if n >= 1: spf[1] = 1
for p in range(2, int(n**0.5)+1):
if spf[p] == p:
for x in range(p*p, n+1, p):
if spf[x] == x: spf[x] = p
return spf
def factorize(x, spf):
out = {}
while x > 1:
p = spf[x]
out[p] = out.get(p, 0) + 1
x //= p
return out
Correctness sketch
- If p has no smaller prime mark, p is prime.
- Every p-multiple below p² already has a smaller factor, so starting at p² misses no new composite.
- Primes write SPF in increasing order, making the first writer minimal.
- Repeated division removes one prime factor at a time and reconstructs the original product.
Complexity
| Time | Space | Parameters |
|---|
| O(n log log n) classic sieve; O(log x) per SPF factorization | O(n) | preprocessing bound n and factored value x<=n |
Edge cases
- Zero and one are not prime
- The loop is empty for n<2
- p² may overflow fixed-width integers
- A factorized input must fit the table
- Repeated prime factors need exponent counts
Error patterns
| Pattern | Why it fails / fix |
|---|
| Starting every mark at 2p | Correct but redundant; values below p² were handled earlier. |
| Treating one as prime | Initialization must exclude it. |
| Overwriting SPF with larger factors | Write only uninitialized entries. |
Selection and exclusion rules
- All primes in a range: sieve.
- Many factorizations under a moderate bound: SPF.
- One small integer: trial division may be cheaper.
- One huge integer: do not blindly sieve to the input bound.
Original micro-example
| Part | Detail |
|---|
| Result | 28=2²×7. |
| Scenario | Precompute through 30 and factor 28. |
| Walkthrough | SPF[28]=2 twice, leaving 7 whose smallest factor is itself. |
Recall prompts
My notes