smooth number

A $k$-smooth number $n$ is an integer such that its prime divisors are less than $k$. For example, 14824161510814728 is 7-smooth since its prime factors are just 2 and 3 (and thus its divisors are all either powers of those two primes or multiples of 6).

For small $k$, the number of smooth numbers less than a given $x$ can be estimated with the formula

$$\frac{1}{\pi (k)!}\prod _{i=1}^{\pi (k)}\frac{\log x}{\log p_i},$$

where $\pi (x)$ is the prime counting function and $p_i$ is the $i$th prime.

Smooth numbers have many applications, such as the many classic factorization algorithms which specifically call for smooth numbers in their initialization steps, as well as fast Fourier transform algorithms that also require smooth numbers.