nを割り切る最大の平方数をなるべく速く見つけるには？

Question

nを割り切る最大の平方数をなるべく速く見つけるにはどうすればよいでしょう？

以下は、[√n] × [√n]から大きい順に調べてみるコードです。

def f(n)
  i = Math.sqrt(n).to_i
  while n % (i * i) > 0
    i -= 1
  end
  i * i
end

p f(108)
p f(109)

Answer 1

素因数分解する方法で取りあえず書いてみましたが、速度計測はしてません。

require "prime"

def foo(n)
  Prime.int_from_prime_division(
    n.prime_division.map { |p,q| [p,q/2*2] }
  )
end

追記：
1から100万まで実行して計測してみました。

require "benchmark"
n = 1_000_000
Benchmark.bm do |x|
  x.report { 1.upto(n) do |i|; f(i); end }
  x.report { 1.upto(n) do |i|; foo(i); end }
end
#=>    user     system      total        real
  64.900000   0.030000  64.930000 ( 64.934020)
  50.840000   0.000000  50.840000 ( 50.853634)

Answer 2

速いかどうかわかりませんが・・・
nを2から順に・・・
0. 割れるだけ割る
0. 割った数^(割ることができた回数/2(整数))を積算していく
すべて割り切った時，2.の全体の積の2乗が，求める「nを割り切れる最大の平方数」になる

例えば108 = 2^2 * 3^3 なので，
2^(2/2) * 3^(3/2) = 2 * 3 = 6
これを2乗して，36が求める平方数になります．

Answer 3

参考までに・・・
平方数かどうかを高速に判定する方法