Учитывая положительное целое число n, найдите наибольшее целое число a, так что a * a делит n.
Если вы знаете факторизацию n, это довольно тривиально.Вопрос в том, может ли это быть сделано асимптотически быстрее, чем разложение n, используя самый известный метод?Есть ли полиномиальный алгоритм?(полином по длине в битах n)
Например, с алгоритмом rho Полларда для факторизации он будет работать в O (n ^ (1/4)), но я ищу лучшего.