 Smallest prime factor

For an integer $n\ge 2$, its smallest prime factor $\mathrm{spf}(n)$ is the least prime divisor of $n$. If $n$ is prime, it equals $n$; if $n$ is composite, it is at most $\sqrt{n}$, because otherwise every product of two prime factors would exceed $n$.

For example, $\mathrm{spf}(91)=7$. A sieve can tabulate smallest prime factors for all integers up to a bound. Repeatedly replacing $n$ by $n/\mathrm{spf}(n)$ then produces its prime factorization. The value at one is a sentinel convention in implementations, since one has no prime factor.