实现这一点的一种方法是对于自然数
(1,..,n)n1,..,n您可以使用埃拉托斯特尼筛法的修改版本：
取一个布尔数组 1..n;
预先计算所有小于n的方格；那是 O(sqrt(N));
对于每个正方形及其倍数，使布尔数组条目为 false...
来自 http://mathworld.wolfram.com/Squarefree.html
没有已知的多项式时间 识别squarefree的算法 整数或用于计算 整数的无平方部分。在 事实上，这个问题可能并不容易 比一般的整数问题 因式分解（显然，如果 整数可以完全因式分解， 是 squarefree 当且仅当它不包含 重复因素）。这个问题是 一个尚未解决的重要问题 数论因为计算 代数的整数环 数域可简化为计算 整数的无平方部分 （Lenstra 1992，Pohst 和 Zassenhaus 1997).
想到的最直接的事情就是列出最多n个素数，并且每个素数最多选择一个。对于大 n 来说这并不容易（例如这里有一个算法），但我也不确定这个问题是不是。
一种方法是使用筛子，类似于埃拉托色尼的筛子。
@Will_Ness 用 Python 编写了一个“快速”素数筛，如下所示。
from itertools import count
# ideone.com/
def postponed_sieve(): # postponed sieve, by Will Ness
yield 2; yield 3; yield 5; yield 7; # original code David Eppstein,
sieve = {} # Alex Martelli, ActiveState Recipe 2002
ps = postponed_sieve() # a separate base Primes Supply:
p = next(ps) and next(ps) # (3) a Prime to add to dict
q = p*p # (9) its sQuare
for c in count(9,2): # the Candidate
if c in sieve: # c's a multiple of some base prime
s = sieve.pop(c) # i.e. a composite ; or
elif c < q:
yield c # a prime
continue
else: # (c==q): # or the next base prime's square:
s=count(q+2*p,2*p) # (9+6, by 6 : 15,21,27,33,...)
p=next(ps) # (5)
q=p*p # (25)
for m in s: # the next multiple
if m not in sieve: # no duplicates
break
sieve[m] = s # original test entry: ideone.com/WFv4f
只需付出一点努力，这就可以用于弹出无平方整数，使用推迟的_sieve()作为筛选尽可能少的平方的基础：
def squarefree(): # modified sieve of Will Ness
yield 1; yield 2; yield 3; # original code David Eppstein,
sieve = {} # Alex Martelli, ActiveState Recipe 2002
ps = postponed_sieve() # a base Primes Supply:
p = next(ps) # (2)
q = p*p # (4)
for c in count(4): # the Candidate
if c in sieve: # c's a multiple of some base square
s = sieve.pop(c) # i.e. not square-free ; or
elif c < q:
yield c # square-free
continue
else: # (c==q): # or the next base prime's square:
s=count(2*q,q) # (4+4, by 4 : 8,12,16,20...)
p=next(ps) # (3)
q=p*p # (9)
for m in s: # the next multiple
if m not in sieve: # no duplicates
break
sieve[m] = s
速度非常快，在我的笔记本电脑上大约 0.8 秒就踢出了第一个 100 万。
毫不奇怪，这表明这实际上与筛选素数是相同的问题，但密度更大。
您可能应该研究一下阿特金筛。当然，这消除了所有非素数（不仅仅是完全平方数），因此可能比您需要的工作量更多。
谷歌搜索了一下，我发现了这个page，其中解释了 J 程序。作为复杂语法的一部分，该算法允许检查一个数字是否是无平方数：
生成完美正方形PS列表，
将你的数字 N 除以 列表中的数字 PS
您可以用您喜欢的语言实现该算法，并对从 1 到 n 的任何数字进行迭代。
http://www.marmet.org/louis/sqfgap/
查看“基本算法：埃拉托斯特尼筛法”部分，这是Armen建议的。下一节是“算法的改进”。
此外，FWIW、Moebius 函数和无平方数是相关的。
我找到了一个更好的算法来计算 [n,m] 等区间内有多少个无平方数。我们可以得到小于
sqrt(m)O(sqrt(m))这是一个简单的 Python 实现：
import math
def squarefree(n):
t=round(math.sqrt(n))
if n<2:
return True
if t*t==n:
return False
if t<=2:
return True
for i in range(2,t):
if n%(i*i)==0:
return False
else:
return True
根据@Armen 的解决方案，我们可以使用埃拉托斯特尼筛法的修改形式。这是一个 C++ 实现，没有使用动态数组：
vector<unsigned> squarefree_eratosthenes(unsigned n) {
unsigned count = n - 1;
bool squarefree[n + 1];
memset(squarefree, 1, sizeof(squarefree));
for (int p = 2; p*p <= n; p++) {
if (squarefree[p*p]) {
for (int i = p*p; i <= n; i += p*p) {
count -= squarefree[i];
squarefree[i] = false;
}
}
}
vector<unsigned> sieved(count,0);
count = 0;
for (int p = 2; p <= n; p++) {
if (squarefree[p]) {
sieved[count] = p;
count++;
}
}
return sieved;
}