Getting a list of square-free numbers
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
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...