The Secret Life of Numbers: Primes, Factorials and Counting

There is a kind of math that feels less like a subject and more like gossip about numbers. Which ones are prime and refuse to break apart. Which ones are secretly a stack of smaller numbers. How many ways you can pick a team, or arrange a shelf, or seat your friends. This is the corner of math I keep coming back to, so let me introduce you to the personalities.

Counting without counting

Start with the friendliest question in all of math: in how many ways can something happen? If you have $n$ distinct things and you want to line them all up, the answer is the factorial:

The logic is a small story. The first slot has $n$ choices, the next has $n-1$ left, then $n-2$, all the way down to one. Multiply the choices and you get $n!$. Five books on a shelf can be arranged in $5! = 120$ ways, which is already more than you would ever try by hand. Factorials grow terrifyingly fast, and that speed is half their charm.

Often you do not want to arrange everything, only to choose a group where order does not matter. Picking three friends for a trip is the same group no matter what order you name them. That is a combination, written $\binom{n}{k}$, and it counts the $k$-element subsets of an $n$-element set:

By convention $\binom{n}{0} = 1$, because there is exactly one way to choose nothing: take the empty group. That is not a technicality to memorize, it is the formula being honest. There genuinely is one way to pick no one, and the math politely agrees.

Combinations have a gorgeous self-referential rule called Pascal's recurrence, and it is my favorite one-line proof in school math:

Read it as a decision. Point at one specific person. Either they are in your group, and you must choose the remaining $k-1$ from the other $n-1$ people, or they are out, and you choose all $k$ from the other $n-1$. Every possible group falls into exactly one of those two piles, so you add them. That is the whole proof, told as a choice, and it is why Pascal's triangle builds itself by adding neighbors.

One last delight before we move on. If you add up the number of groups of every possible size, from choosing nobody to choosing everybody, you get a clean power of two:

The reason is almost too simple: every person is either in or out, that is two choices each, so $2^n$ total subsets. Counting the same thing two different ways and getting a formula for free is the entire sport of combinatorics, and once you feel it, you cannot unfeel it.

The atoms of every number

Now meet the primes, the numbers that refuse to be built from smaller pieces. A prime is a whole number greater than one whose only divisors are one and itself. Two, three, five, seven, eleven, and on forever. They are the atoms of arithmetic, because every other number is a unique product of them.

That last claim has a name, the fundamental theorem of arithmetic, and it says any number greater than one factors into primes in exactly one way:

Twelve is $2^2 \cdot 3$. A hundred is $2^2 \cdot 5^2$. There is no second recipe, no alternate spelling. Every number has one true chemical formula, and finding it is called factorization. Here is the tidy way to compute it, dividing out each factor completely before moving on:

void factorize(int n) {
    for (int d = 2; (long long)d * d <= n; d++) {
        int power = 0;
        while (n % d == 0) { power++; n /= d; }
        if (power > 0) cout << d << "^" << power << " ";
    }
    if (n > 1) cout << n << "^1";
}

Once you have that prime recipe, the number stops keeping secrets. The count of its divisors comes straight from the exponents, because each prime can appear anywhere from zero up to its full power:

For twelve that is $(2+1)(1+1) = 6$, and sure enough its divisors are one, two, three, four, six and twelve. You did not have to hunt for them one by one. The prime factorization handed you the count directly, which is the recurring joy of number theory: break a number into atoms, and its properties fall out for free.

The same trick gives the sum of all divisors in one formula, no searching required:

I love this because it is the opposite of brute force. The lazy way is to test every candidate divisor and add up the ones that fit. The elegant way is to understand the structure once and read the answer off the exponents. Learning to prefer the second way is most of what growing as a programmer feels like.

Hunting primes without wasting your life

So how do you check whether a number is prime? The obvious method is to try dividing by everything below it. It works, and it is painfully slow, testing every number from two up to $n-1$. The first real improvement is noticing you never need to look past the square root.

The reason is a small piece of logic worth keeping. If $n$ has a divisor larger than $\sqrt{n}$, it must also have a matching partner smaller than $\sqrt{n}$, because the two multiply to $n$. So if no small divisor exists, no large one can either. You can stop at the square root and lose nothing:

There is an even cheekier speedup. Every prime bigger than three sits in one of two lanes, the numbers of the form $6k-1$ or $6k+1$. Everything else is divisible by two or by three and cannot be prime. So after handling the small cases you only ever test those two lanes, skipping two thirds of the candidates:

bool is_prime(int n) {
    if (n < 2) return false;
    if (n == 2 || n == 3 || n == 5) return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;
    int r = (int)sqrt((double)n);
    for (int k = 1; 6 * k - 1 <= r; k++) {
        if (n % (6 * k - 1) == 0) return false;
        if (n % (6 * k + 1) == 0) return false;
    }
    return true;
}

That is a genuinely nice piece of code, and it tells a small story about optimization. The first version was correct. The square root version was correct and faster. The $6k \pm 1$ version is correct and faster still, and each step came not from cleverer code but from understanding the numbers better. The math did the optimizing. The code just wrote down what the math already knew.

I want to be honest about a limit here, because pretending otherwise is how people get burned. This method is wonderful for the numbers you meet in school and in most everyday problems. For the gigantic primes behind real cryptography, mathematicians use much deeper tests, because trial division by lanes would outlast the universe. Knowing where your tool stops working is as important as knowing how it works.

Primes in code: the fuller toolbox

Checking one number is only the beginning. Real programs want every prime up to a limit, or a count, or the next prime after some point, and each of those has its own favorite tool. When you need all the primes up to $N$, nothing beats the Sieve of Eratosthenes. Instead of testing numbers one at a time, you find a prime and cross out all of its multiples in one sweep.

#include <vector>
using namespace std;
 
vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; (long long)p * p <= n; p++)
        if (is_prime[p])
            for (int m = p * p; m <= n; m += p)
                is_prime[m] = false;
    return is_prime;
}

Two small details carry the whole idea. You only sieve while $p^2 \le n$, because any composite past that point has already been crossed out by a smaller prime. And you start crossing at $p^2$ rather than $2p$, since every smaller multiple of $p$ was handled by an earlier prime. Those two tweaks turn a naive quadratic loop into something that runs in about $O(n \log \log n)$, which is close enough to linear that you will not feel the difference.

Once you have that boolean map, the rest is easy. Counting the primes up to a limit, summing them, or listing them are all one pass over the sieve.

int count_primes(int n) {
    vector<bool> prime = sieve(n);
    int count = 0;
    for (int i = 2; i <= n; i++)
        if (prime[i]) count++;
    return count;
}
 
long long sum_primes(int n) {
    vector<bool> prime = sieve(n);
    long long total = 0;
    for (int i = 2; i <= n; i++)
        if (prime[i]) total += i;
    return total;
}

When you want the next prime after some value rather than a whole table, the sieve is overkill, and you fall back to testing candidates one by one with the fast single-number check from earlier. This is the honest tradeoff of the toolbox: the sieve wins when you want many primes at once, and trial division wins when you want one prime near a specific spot.

int next_prime(int n) {
    int candidate = n + 1;
    while (!is_prime(candidate)) candidate++;
    return candidate;
}

Primes also drive two workhorses you cannot avoid: the greatest common divisor and the least common multiple. Two numbers are coprime exactly when they share no prime factors, which is the same as saying their gcd is one. You could factor both and compare, but Euclid found something far faster two thousand years ago, and it is still the code we write today.

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
 
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

Notice that lcm divides before it multiplies. That ordering is not cosmetic, it keeps the intermediate value small and dodges an overflow that the more obvious a * b / gcd(a, b) would walk straight into. It is exactly the kind of quiet, correct decision that separates code that passes the demo from code that survives real inputs.

Finally, the confession from before deserves a real answer. For the enormous numbers behind cryptography, trial division would outlast the universe, so we lean on Fermat's little theorem: if $p$ is prime, then for any $a$ not divisible by $p$,

To use that on huge numbers you need to raise to a power under a modulus without the value exploding, which is fast modular exponentiation by squaring. Test a few bases and a composite almost always gives itself away.

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}
 
bool probably_prime(long long n) {
    if (n < 2) return false;
    for (long long a : {2, 3, 5, 7, 11}) {
        if (n % a == 0) return n == a;
        if (mod_pow(a, n - 1, n) != 1) return false;
    }
    return true;
}

The name probably_prime is doing honest work. This test can be fooled by rare liars, so serious libraries stack more bases or switch to stronger tests, but the shape is exactly what real systems use. Notice the arc across this whole section: a sieve for many small primes, trial division for one nearby prime, Euclid for shared factors, and Fermat for giants. There is no single best way to work with primes, only the right tool for the size of the question, and knowing which to reach for is most of the skill.

Factorials and the zeros at the end

Here is a puzzle that looks impossible and turns out to be gentle. How many zeros are at the end of $100!$? You obviously cannot multiply it out, the number has more than a hundred and fifty digits. But you do not have to. A trailing zero is made by a factor of ten, a ten is a two times a five, and factorials have far more twos than fives, so the number of trailing zeros is simply the number of fives hidden inside.

Counting those fives is Legendre's formula, which gives the exact power of any prime $p$ inside $n!$:

Those angle brackets mean "round down." The idea is lovely: first count every multiple of $p$ up to $n$, then add an extra count for multiples of $p^2$ because they contribute a second factor, then $p^3$ for a third, and so on. The sum looks infinite but goes quiet the moment $p^i$ passes $n$. For trailing zeros you set $p = 5$:

int trailing_zeros(int n) {
    int count = 0;
    for (long long p = 5; p <= n; p *= 5)
        count += n / p;
    return count;
}

Run it for a hundred and you get twenty-four. That means $100!$ ends in exactly twenty-four zeros, a fact you now know for certain without ever computing the monster itself. I find that genuinely thrilling. You reached inside a number too big to write and pulled out a precise truth using nothing but division and a good idea.

That is the whole spirit of this branch of math, really. You almost never bludgeon a number into submission. You understand its structure, its primes, its factors, its hidden fives, and then the hard question quietly answers itself. The best code I write in this world is short, because the math around it is doing the heavy lifting.

Conclusion

Numbers are not the flat, gray things they get painted as in a hurry through a textbook. Some are unbreakable atoms, some are stacks of those atoms with predictable properties, some exist only to count the ways a thing can happen. Combinations, primes, factorizations and factorials are less a list of formulas and more a cast of characters, each with a trick worth knowing.

And the recurring lesson, the one that made me a better programmer as much as a better student, is this: understand the structure first, and the computation gets small. Do not chase every divisor when the exponents already know the answer. Do not multiply out the factorial when the fives are all you need. Learn the personalities of numbers, and they start doing your work for you.