4

一种方法是对自然数 (1,.., n ) 进行因式分解，看看它们是否有任何重复的素因数，但是对于大的n会花费很多时间。那么有没有更好的方法可以从 1,.., n中获取无平方数？

4

9 回答 9

12

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

取一个布尔数组 1.. n ;

预计算所有小于 n 的方格；那是 O(sqrt(N));

对于每个正方形及其倍数，使布尔数组条目为假...

于 2011-03-15T14:37:03.783 回答
7

想到的最直接的事情是列出最多 n 的素数，并且每个素数最多选择一个。这对于大 n 来说并不容易（例如，这里有一个算法），但我也不确定这个问题是否存在。

于 2011-03-15T14:34:23.680 回答
7

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

没有已知的多项式时间算法可用于识别无平方整数或计算整数的无平方部分。事实上，这个问题可能并不比整数分解的一般问题更容易（显然，如果一个整数可以完全分解，则当它不包含重复因数时，它是无平方的）。这个问题是数论中一个重要的未解决问题，因为计算代数数域的整数环可以简化为计算整数的无平方部分（Lenstra 1992，Pohst 和 Zassenhaus 1997）。

于 2011-03-15T14:37:10.560 回答
2

一种方法是使用类似于 Eratosthenes 的筛子。

@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 秒内踢出第一个百万。

不出所料，这表明这与筛选素数实际上是相同的问题，但密度要大得多。

于 2015-11-24T17:55:32.730 回答
0

您可能应该查看Atkin 的筛子。当然，这消除了所有非素数（不仅仅是完美的正方形），所以它可能比你需要的更多。

于 2011-03-15T14:36:19.200 回答
0

谷歌搜索了一下，我发现这个页面解释了一个 J 程序。作为复杂语法的一部分，该算法允许检查一个数字是否是无平方的：

  • 生成完美正方形 PS 的列表，

  • 取你的数字 N 并除以列表 PS 中的数字

  • 如果列表中只有 1 个整数，则 N 是无平方的

您可以用您喜欢的语言实现该算法，并在从 1 到 n 的任何数字上对其进行迭代。

于 2011-03-15T15:07:25.723 回答
0

http://www.marmet.org/louis/sqfgap/

查看“基本算法：Eratosthenes 的筛子”部分，这是 Armen 建议的。下一节是“算法的改进”。

此外，FWIW、莫比乌斯函数和无平方数是相关的。

于 2011-03-15T15:35:02.570 回答
0

我找到了一种更好的算法来计算区间中的无平方数，例如 [n,m]。我们可以得到小于 的素数sqrt(m)，然后我们应该减去那些素数平方的倍数，然后加上每个两个素数乘积小于 m 的倍数，然后减去树，然后再加上 4....最后我们会得到答案。当然它运行在O(sqrt(m)).

于 2012-09-01T02:29:20.020 回答
0 
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
于 2017-09-25T06:10:32.160 回答