Нет быстрого алгоритма для этого. Требуется найти все квадратные факторы. Это требует хотя бы некоторого факторинга.
Но вы можете немного ускорить свой подход. Для начала вам нужно только найти простые множители вплоть до корня куба от n, а затем проверить, является ли 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)