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...