Getting a list of square-free numbers

Question

One way to get that is for the natural numbers (1,..,n) we factorise each and see if they have any repeated prime factors, but that would take a lot of time for large n. So is there any better way to get the square-free numbers from 1,..,n ?

Answer 1

You could use Eratosthenes Sieve's modified version:

Take a bool array 1..n;

Precalc all squares that are less than n; that's O(sqrt(N));

For each square and its multiples make the bool array entry false...

Answer 2

From http://mathworld.wolfram.com/Squarefree.html

There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer. In fact, this problem may be no easier than the general problem of integer factorization (obviously, if an integer can be factored completely, is squarefree iff it contains no duplicated factors). This problem is an important unsolved problem in number theory because computing the ring of integers of an algebraic number field is reducible to computing the squarefree part of an integer (Lenstra 1992, Pohst and Zassenhaus 1997).