Approximating the number of integers free of large prime factors

Abstract:

Define $\Psi (x,y)$ to be the number of positive integers $n\le x$ such that $n$ has no prime divisor larger than $y$. We present a simple algorithm that approximates $\Psi (x,y)$ in $O(y\{\frac {\log \log x}{\log y} + \frac 1{\log \log y}\})$ floating point operations. This algorithm is based directly on a theorem of Hildebrand and Tenenbaum. We also present data which indicate that this algorithm is more accurate in practice than other known approximations, including the well-known approximation $\Psi (x,y)\approx x\rho (\log x/\log y)$, where $\rho (u)$ is Dickman’s function.