# Sieving primes from squarefrees

Is there any efficient way of sieving prime numbers from the set of squarefree numbers? If so, is this any simpler a task than sieving from the set of natural numbers?

-
It is easier to start with the natural numbers than computing first the list of square-free numbers, I think. – Dietrich Burde Nov 28 '13 at 19:13
Lets just say, for sake of argument, that you have an infinite list of squarefree numbers at your disposal. Is it any easier to sieve prime numbers from this hypothetical list than from the entire set of natural numbers? – martin Nov 28 '13 at 19:16
Sieving all positive integers, or all positive integers that aren't multiple of any of a set of small primes, is simpler, because you just mark the multiples of the prime you're currently treating. You don't need to care whether that multiple is squarefree, you have a simple way of getting from one multiple to the next. Considering only squarefree multiples of the primes adds complication. I have no proof, but I'd be very surprised if one found a way to make the small gain one has from the fact that there are fewer squarefree numbers outweigh the added complication. – Daniel Fischer Nov 28 '13 at 19:26

Even if you had a magic function that returned the $n$th square-free integer in zero time, I don't see how you could use it to build a sieve. And of course there is no such magic function.
So given this hypothetical magic function (or, if an algorithm were discovered that returned the $n$th squarefree number in polynomial time), would it be no simple to sieve primes from this than from the set of natural numbers? – martin Nov 28 '13 at 19:19