Prime factor

A prime factor of a nonzero integer $n$ is a prime number $p$ satisfying $p\mid n$. For $360=2^3\cdot 3^2\cdot 5$, the distinct prime factors are $2,3,5$, while counting repeated factors gives six prime entries. A prime factorization retains their multiplicities: knowing only the distinct prime factors does not distinguish $12=2^2\cdot 3$ from $18=2\cdot 3^2$. A negative integer has the same prime factors as its absolute value.

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.