Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What is there to prove? Do you want to find the number of square-free numbers smaller than 201? –  Srivatsan Oct 18 '11 at 2:42
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$. –  André Nicolas Oct 18 '11 at 2:44

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
+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). –  Ross Millikan Oct 18 '11 at 4:27

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.