complexity-theory - 随机存取机 (RAM) - 测试无平方 n

Question

我正在使用测试给定自然数是否无平方的模拟器编写随机存取机 (RAM)。我的目标是然后分析它的复杂性。

在高层次上，我将使用以下测试功能

def isSquareFree(n):

    if n % 2 == 0:
        n = n / 2

    if n % 2 == 0:
        return False

    for i in range(3, int(sqrt(n) + 1)):
        if n % i == 0:
            n = n / i

        if n % i == 0:
            return False

return True

我的问题是，我不确定如何使用 RAM 命令计算 n 的平方根，并且在网上找不到太多资源。所以我正在重新考虑这是否真的是正确的做法。

测试自然数是否无平方的替代方法有哪些，可以使用 RAM 实现？

谢谢。

Answer 1

如果你只是想避免 sqrt在您的代码中，您可以简单地测试 i*i<=n .无论如何，这可能是一个好主意，因为计算平方根是一件非常困难的事情。
因此，我会将您的代码更改为:

def isSquareFree(n):
    i=2   
    while i*i <= n:
        if n % i == 0:
            n = n / i

        if n % i == 0:
            return False
        
        i = i+1

    return True

上面只使用了漂亮的原子操作，所以我希望这会对你有所帮助。但我不熟悉 RAM 编程，所以我不确定这是否能解决您的问题。