最快得到确切的答案的算法（不近似）当平方根

对不起，我不清楚头衔，但我不知道如何陈述得当（随意编辑），所以我会给例如：最快得到确切的答案的算法（不近似）当平方根

开方（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，当然我会用适当的语法

来源

2011-02-18 Templar

任何整数分解算法会做什么，但他们难以实现。是什么让你觉得上述不会足够快达到你的目的？在现实世界中，速度最快！=如果对于手头的问题来说太难了，并且没有必要，那么最好。 – mellamokb 2011-02-18 16:12:39

这个算法似乎并不适用于更有趣的情况，比如2700. – 2011-02-18 16:38:31

是的我的意思是最实际的 – Templar 2011-02-18 16:47:28

对此没有快速算法。它要求你找到所有的方形因素。这至少需要一些分解。

但是你可以加快你的方法很多。首先，你只需要找到n的立方根，然后用Fastest way to determine if an integer's square root is an integer的建议测试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-18 16:57:00 btilly