Intuition, Vocabulary and Foundations
A prime is an integer greater than $1$ with exactly two positive divisors: $1$ and itself. Composite integers have additional divisors, while $1$ is neither prime nor composite. The Fundamental Theorem of Arithmetic says every $n>1$ has a unique representation
$$ n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} $$
apart from factor order. For example, $360=2^3\cdot3^2\cdot5$.
Every divisor of $360$ is $2^{f_1}3^{f_2}5^{f_3}$ with $0\le f_1\le3$, $0\le f_2\le2$, and $0\le f_3\le1$. Independent exponent choices give
$$ \tau(n)=\prod_{i=1}^{k}(e_i+1), $$
so $\tau(360)=24$. Summing each allowed prime power gives
$$ \sigma(n)=\prod_{i=1}^{k}\left(1+p_i+\cdots+p_i^{e_i}\right) =\prod_{i=1}^{k}\frac{p_i^{e_i+1}-1}{p_i-1}. $$
Thus $\sigma(360)=15\cdot13\cdot6=1170$. The proper-divisor sum is $\sigma(n)-n$ and classifies an integer as deficient, perfect, or abundant.
Prime factorization turns multiplicative questions into independent exponent choices. Once $n=\prod p_i^{e_i}$ is known, divisibility becomes exponent comparison, divisor enumeration becomes a Cartesian product, and $\tau$ and $\sigma$ become products of local contributions.
| Concept | Formal meaning | Example | Boundary or non-example | Question answered |
|---|---|---|---|---|
| Prime | Integer $p>1$ with exactly two positive divisors | $29$ is prime | $1$ is neither prime nor composite | Is the integer indivisible? |
| Composite | Integer $n>1$ with a nontrivial divisor | $35=5\cdot7$ | A prime has no such split | Can it be factored further? |
| Factorization | Unique $n=\prod p_i^{e_i}$ | $360=2^3\cdot3^2\cdot5$ | Reordering changes nothing | Which prime powers construct $n$? |
| Divisor | Positive $d$ with $d\mid n$ | $24\mid360$ | $14\nmid360$ | Does $d$ divide exactly? |
| Prime exponent | Largest $e$ with $p^e\mid n$ | $v_2(360)=3$ | Missing primes have exponent $0$ | How many copies of $p$ occur? |
| Divisor count | $\tau(n)=\prod(e_i+1)$ | $\tau(360)=24$ | $\tau(1)=1$ | How many divisors exist? |
| Divisor sum | Product of prime-power geometric sums | $\sigma(12)=28$ | Proper sum is $\sigma(n)-n$ | What do all divisors sum to? |
| Square-free | Every exponent is at most $1$ | $30=2\cdot3\cdot5$ | $12$ is not square-free | Does a squared prime divide $n$? |
Step-by-Step Derivations and Algorithms
Trial division tests candidates in increasing order. When $p$ divides the current residual, divide repeatedly and record the exponent. The extracted prime powers times the residual always equal the original input.
If composite $m=ab$, at least one factor is no greater than $\sqrt m$; otherwise $ab>m$. To avoid overflow from $p^2$, use the equivalent condition
$$ p\le\frac{m}{p}. $$
Use the shrinking residual $m$, not only the original input. When the loop stops, any residual greater than $1$ is prime; otherwise it would possess a factor in the tested range.
After extracting $2$ and $3$, every larger prime is congruent to $1$ or $-1$ modulo $6$. Testing $6k\pm1$ candidates skips multiples of $2$ and $3$ but still requires divisibility checks.
Generate divisors incrementally. Begin with $[1]$; for each $p^e$, multiply existing partial divisors by $1,p,\ldots,p^e$. After each stage, the list contains exactly the divisors formed from processed primes.
flowchart TD
A["Positive integer n"] --> B{"n equals 1?"}
B -->|Yes| C["Empty factorization"]
B -->|No| D["Extract powers of 2 and 3"]
D --> E["Test 6k minus 1 and 6k plus 1"]
E --> F{"Candidate within square-root bound?"}
F -->|Yes| G["Extract complete exponent"]
G --> E
F -->|No| H{"Residual greater than 1?"}
H -->|Yes| I["Record residual prime"]
H -->|No| J["Factorization complete"]
I --> J
J --> K["Compute tau and sigma"]
J --> L["Generate exponent combinations"]
Trial division preserves that extracted prime powers times the residual equal the original input and that the residual has no prime factor below the next candidate. It takes $O(\sqrt n)$ divisibility tests in the worst case, while listing divisors requires $\Theta(\tau(n))$ output work.
Implementation, Complexity and Engineering
This API accepts positive integers, returns the empty factorization for $1$, and rejects zero and negatives. Signed applications should store the sign separately rather than treating $-1$ as a positive prime.
It extracts $2$ and $3$, then alternates steps of $2$ and $4$ through $6k\pm1$. The overflow-safe condition compares the candidate with the residual divided by the candidate. Divisor statistics use exponents directly; generation occurs only when the divisor values are required.
| Concern | Fragile approach | Robust approach | Complexity | Failure prevented |
|---|---|---|---|---|
| Input domain | Factor zero or negatives silently | Require $n\ge1$ | $O(1)$ validation | Infinite loops and ambiguity |
| Integer one | Treat $1$ as prime | Return the empty factorization | $O(1)$ | Broken uniqueness |
| Stopping test | Use $p^2\le n$ in fixed width | Use $p\le n/p$ on the residual | $O(1)$ per candidate | Overflow and excess work |
| Candidates | Test every integer | Extract $2,3$, then test $6k\pm1$ | $O(\sqrt n)$ worst case | Unnecessary tests |
| Exponents | Record a prime once | Divide until it no longer divides | $O(e)$ for exponent $e$ | Lost multiplicity |
| Final residual | Discard it | Record it when greater than $1$ | $O(1)$ | Missing a large prime |
| Divisor count | Generate all divisors | Compute $\prod(e_i+1)$ | $O(k)$ | Avoidable output work |
| Generation | Scan every integer | Expand exponent choices | $\Theta(\tau(n))$ | Full-range scan |
| Divisor sum | Add generated divisors | Multiply geometric sums | $O(k)$ | Unnecessary enumeration |
Applications, Case Studies and Exercises
Prime exponents turn structural questions into small combinatorial calculations. They reveal grid dimensions, sharding factors, scheduling periods, and multiplicative statistics without scanning every integer up to the input.
Apply Primes, Factorization & Divisor Structure
Case study 1 — Arrange 360 participants
- Factor $360=2^3\cdot3^2\cdot5$.
- Compute $\tau(360)=24$ possible row lengths.
- Pair each divisor $d$ with $360/d$.
- Conclude that there are $12$ unordered rectangles because $360$ is not a square.
- Generate the divisors and verify the result.
Success criterion: derive the count from exponents and confirm it by generation.
Case study 2 — Choose a production shard count
A system distributes $45{,}360$ records evenly across between $32$ and $256$ shards.
- Factor $45{,}360=2^4\cdot3^4\cdot5\cdot7$.
- Compute $\tau(45{,}360)=100$.
- Generate divisors and filter them to the permitted interval.
- For each candidate $d$, calculate the exact load $45{,}360/d$.
- Select using operational constraints such as worker count and memory.
Success criterion: produce every feasible shard count and verify exact divisibility.
Tiered exercises
- Recall: Classify $1,2,49,97$, and $221$.
- Factorization: Factor $7560$ and reconstruct it.
- Divisor count: Compute $\tau(7560)$ without listing divisors.
- Divisor sum: Derive $\sigma(72)$ from $72=2^3\cdot3^2$.
- Proof: Show that a number is a square exactly when every prime exponent is even.
- Debugging: Explain why a fixed original square-root bound may do excess work.
- Overflow: Replace $p^2\le n$ with an overflow-safe test.
- Implementation: Yield divisors lazily without sorting.
- Extension: Derive the number of square-free divisors.
- Benchmark: Compare odd-only trial division with the $6k\pm1$ wheel.
Use trial division for moderate individual inputs, exponent formulas when only statistics are needed, and output-sensitive generation when divisors themselves are required. Treat $1$, the final residual prime, overflow-safe stopping, and output size explicitly; the next topic extends these ideas to bulk prime and factor precomputation with sieves.
Next in the Series
In Sieves & Bulk Precomputation, we'll explore Precompute prime and factor information at scale..