2

抱歉标题不清楚，但我不知道如何正确说明（随意编辑），所以我举个例子：

sqrt(108) ~ 10.39... 但我希望它像这样 sqrt(108)=6*sqrt(3) 所以这意味着扩展为两个数字

这就是我的算法

i = floor(sqrt(number))                  //just in case, floor returns lowest integer value :)
while (i > 0)                            //in given example number 108
  if (number mod (i*i) == 0)
    first = i                            //in given example first is 6
    second = number / (i*i)              //in given example second is 3
    i = 0
  i--

也许你知道更好的算法？

如果重要，我将使用 PHP，当然我会使用适当的语法

4

3 回答 3

3

对此没有快速算法。它要求您找到所有平方因数。这至少需要一些分解。

但是您可以大大加快您的方法。首先，您只需要找到直到 n 的立方根的素数，然后使用Fastest way 的建议来测试 n 本身是否是完美平方，以确定整数的平方根是否为整数。

下一个加速，从底层因素向上工作。每次你找到一个质因数时，将 n 除以它，将平方累加。当你减少 n 的大小时，减少你将要达到的极限。这使您可以利用大多数数字可以被一些小数字整除的事实，这会迅速减少您留给因子的数字的大小，并让您更快地切断搜索。

下一个性能改进，开始变得更聪明地知道你用哪些数字来进行试验划分。例如特殊情况 2，则只测试奇数。您刚刚再次将算法的速度提高了一倍。

但是请注意，即使有了所有这些加速，您也只是获得了更有效的蛮力。它仍然是蛮力，并且仍然不会很快。（尽管它通常会比您当前的想法快得多。）

这里有一些伪代码来说明这一点。

integer_sqrt = 1
remainder = 1

# First we special case 2.
while 0 == number % 4:
    integer_sqrt *= 2
    number /= 4

if 0 == number / 2:
    number /= 2
    remainder *= 2

# Now we run through the odd numbers up to the cube root.
# Note that beyond the cube root there is no way to factor this into
#    prime * prime * product_of_bigger_factors
limit = floor(cube_root(number + 1))
i = 3
while i <= limit:
    if 0 == number % i:
        while 0 == number % (i*i):
            integer_sqrt *= i
            number /= i*i
        if 0 == number % (i*i):
            number /= i
            remainder *= i
        limit = floor(cube_root(number + 1))
    i += 2

# And finally check whether we landed on the square of a prime.

possible_sqrt = floor(sqrt(number + 1))
if number == possible_sqrt * possible_sqrt:
    integer_sqrt *= possible_sqrt
else:
    remainder *= number

# And the answer is now integer_sqrt * sqrt(remainder)

请注意，各种 +1 是为了避免浮点数不精确的问题。

运行 2700 算法的所有步骤，会发生以下情况：

number = 2700
integer_sqrt = 1
remainder = 1

enter while loop
    number is divisible by 4
        integer_sqrt *= 2 # now 2
        number /= 4 # now 675

    number is not divisible by 4
        exit while loop

number is not divisible by 2

limit = floor(cube_root(number + 1)) # now 8
i = 3
enter while loop
    i < =limit # 3 < 8
        enter while loop
            number is divisible by i*i # 9 divides 675
                integer_sqrt *= 3 # now 6
                number /= 9 # now 75

            number is not divisible by i*i # 9 does not divide 75
                exit while loop

        i divides number # 3 divides 75
            number /= 3 # now 25
            remainder *= 3 # now 3

        limit = floor(cube_root(number + 1)) # now 2

    i += 2 # now 5

    i is not <= limit # 5 > 2
        exit while loop

possible_sqrt = floor(sqrt(number + 1)) # 5

number == possible_sqrt * possible_sqrt # 25 = 5 * 5
    integer_sqrt *= possible_sqrt # now 30

# and now answer is integer_sqrt * sqrt(remainder) ie 30 * sqrt(3)
于 2011-02-18T16:57:00.207 回答
2

不太可能有一个快速的算法来解决这个问题。请参阅https://mathoverflow.net/questions/16098/complexity-of-testing-integer-square-freeness特别是https://mathoverflow.net/questions/16098/complexity-of-testing-integer-square-freeness/16100 #16100

于 2011-02-18T16:15:54.237 回答
0
  1. 按升序列出所有素数除数，例如 2700 = 2*2*3*3*3*5*5。这是最慢的一步，需要 sqrt(N) 操作。
  2. 创建一个累加器（从 1 开始）。扫描此列表。对于每一对数字，将累加器乘以它们中的一个。所以扫描上面的列表后，你会得到 2*3*5。
  3. 累加器是您的乘数。其余的仍然在平方根之下。
于 2011-02-18T16:30:13.607 回答