What is the probability that a randomly selected positive integer between $1$ and $100$ (inclusive) is square-free (i.e., has no square factor; for instance $15 = 3 \cdot 5$ is square-free, but $90$ is not, since it has a factor of $3^2$).
I have no idea how to solve this problem. Any help on how to proceed?
Best Answer
I recommend a variant of the Sieve of Eratosthenes. Instead of crossing off the prime numbers, cross of the perfect squares and their multiples. Count the numbers that you don't cross off to get the square free numbers.