Square free Numbers

Python 2: 71 chars

i=n=input()
A=[1]*n
while~-i:A[i*i::i*i]=~-n/i/i*[0];i-=1
print~-sum(A)

Basically an optimization of Keith Randall's solution of zeroing out numbers that are multiples of squares. The main improvement is directly zeroing out the sublist A[i*i::i*i], which requires awkwardly calculating its length or else Python refuses to do the slice assignment.

Lots of ~- are used for -1. The ~-sum(A) corrects for 0 being falsely counted as a squarefree number.

J, 21 chars

+/(]=&#~.)@:q:"0>:i.N

Checks for each integer from 1 to N if any prime factor appears more than once.

eg:

+/(]=&#~.)@:q:"0>:i.10000
 6083
+/(]=&#~.)@:q:"0>:i.100000
 60794

Takes ~3secs for N=1,000,000 (@2GHz,1core)

Python, 84 characters

n=input()
R=range(n)
A=[1]*n
for i in R[2:]:
 for x in R[::i*i]:A[x]=0
print sum(A)