Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
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
2  
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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
    
I believe that's right, yes. –  TonyK Nov 28 '13 at 21:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.