An estimate for the number of integers with no small factors Given integers $x > y$, I am interested in the number of positive integers  $\leq x$ and free of factors $\leq y$.  In my case $x$ and $y$ will be large. For a concrete example we can take $x=2^{100}$ and $y=2^{40}$.
Is there a computationally efficient method to estimate this number?  I was looking at Mertens' third theorem but I can't see how to use it make an efficient algorithm.
I also found On the number of positive integers ≦ x and free of prime factors > y but that is the opposite of what I want. I would like the number of positive integers $\leq x$ and free of factors $\leq y$.
 A: If $y \gt \sqrt[3]x$ you are just looking for primes in the range from $y$ to $x$ plus the pairs of primes greater than $y$ that multiply to less than $x$.  Let $\pi(z)$ be the prime-counting function  For the primes we want $\pi(x)-\pi(y)\approx \operatorname{li}(x)-\operatorname{li}(y)$.  For the pairs of primes we get an estimate by saying that each number $z$ has $\frac 1{\ln(z)}$ chance of being prime.  The number of pairs is then about
$$\int_y^{\sqrt x} dt \frac 1{\ln(t)} \int _t^{\frac xt}du \frac 1 {\ln u}=\int_y^{\sqrt x} dt \frac 1{\ln(t)}\left(\operatorname{li}\left(\frac xt\right) - \operatorname{li}(t)\right)$$
which is an integral with a nice smooth integrand, so it should be easy to evaluate numerically.  If $y$ is between $\sqrt [4]x$ and $\sqrt[3]x$ you can do the same thing but add a triple integral for numbers with three large factors.
A: The general answer to the question you ask is also related to Buchstab function.
Let $\Phi(x,y)$ be the number of positive integers $n\leq x$ which do not have any prime divisor $p< y$.
Then it is known that for any fixed $U>1$
$$
\Phi(x,y)=\frac{x w(u)}{\log y} - \frac y{\log y} +O\left(\frac x{(\log x)^2} \right)
$$
where $y=x^{\frac 1u}$ with $1\leq u\leq U$ , $y\geq 2$, and $w(u)$ satisfies
$$
w(u)=\frac 1u  \ \ \textrm{ for }1\leq u \leq 2, 
$$
$$
(uw(u))'=w(u-1) \ \ \textrm{ for }u>2.
$$
Also, it is known that $w(u)\rightarrow e^{-\gamma}$ as $u\rightarrow\infty$.
See also Montgomery & Vaughan's Multiplicative Number Theory:Classical Theory, in particular Chapter 7.
A: In your case, you are counting the primes > 2^40 and less than 2^100, plus the number of pairs p, q where 2^40 < p <= 2^50 and p <= q < 2^100 / p.
There are fast prime counting algorithms, but the number of primes < 2^100 will take you ages. Let’s say a major investment in computer hardware and some serious programming effort. The number of pairs can be found with a sieve of size 2^60, that will take significant time as well.
And I hear one “graffe” has volunteered to show us how to calculate pi(2^100). Which I believe hasn’t been done yet.
