获取无方形数字列表

Question

获得这个的一种方法是对于自然数(1,...,n)我们将每个因子分解并查看它们是否具有任何重复的素因子,但是对于大n来说这将花费大量时间.那么有没有更好的方法来获得1,...,n的无方格数？

Answer 1

您可以使用Eratosthenes Sieve的修改版本:

拿一个bool阵列1 .. n ;

Precalc小于n的所有正方形; 那是O(sqrt(N));

对于每个方块及其倍数,使bool数组条目为false ...

Answer 2

想到的最直接的事情是将素数列为n并最多选择其中一个.这对于大n来说并不容易(例如这里是一个算法),但我不确定这个问题是什么.

Answer 3

来自http://mathworld.wolfram.com/Squarefree.html

没有已知的多项式时间算法来识别无平方整数或计算整数的无平方部分.事实上,这个问题可能并不比整数分解的一般问题容易得多(显然,如果一个整数可以被完全考虑,如果它不包含重复因子则是无广义的).这个问题在数论中是一个重要的未解决的问题,因为计算代数数字域的整数环可以简化为计算整数的无平方部分(Lenstra 1992,Pohst and Zassenhaus 1997).