0
$\begingroup$

Prove or find the number of squarefree number is less than $201$.

Squarefree: If a number is not divisible by the square of any positive integer, it is squarefree. For example, $21 = 3 \cdot 7$ is a squarefree number and $20 = 2^2 \cdot 5$ is not.

  • 2
    Definition of square-free not quite right, we want not divisible by the square of any integer $\gt 1$. Anything is divisible by $1^2$.2011-10-18

2 Answers 2

2

The computer programmer's answer: set a counter to zero; for each $a$ from 1 to 201 do the following: for each $m$ with $m\ge2$ and $m^2\le a$, see whether $a$ is divisible by $m^2$. If $a$ isn't divisible by any of those numbers $m^2$, add 1 to the counter. When you've gone through all the values of $a$, the counter holds the answer.

It's not pretty, there's plenty of room for optimization, and it won't teach you any Number Theory, but it will get you the answer.

  • 0
    +1 In the spirit of Project Euler, works great for 201, not so well for 10^15, maybe nothing works for 10^100 (to accuracy $\pm$1).2011-10-18
1

Hints: 1)you can consider only the squares of primes (why?) 2) what primes do you have to worry about? 3)how many numbers below $201$ are divisible by the square of each of those primes? 4)what more do you have to worry about?