数字の中で最大の正方形を見つける方法（Java）

Question

数字をこの数字と他の数字の中で最大の正方形の積に分解したいのですが、ある時点で固まっています。私は本当にいくつかの提案を感謝します。これは私がこれまで行ってきたことです：

私は入力に数字をとり、素数に分解し、素数のシーケンスをArrayListに入れます。数字はある意味でソートされているので、シーケンス内の数字は増加しています。

例えば、

996 is 2 2 3 83 
1000 is 2 2 2 5 5 5 
100000 is 2 2 2 2 2 5 5 5 5 5 

私の考えは今、シーケンス内の各要素の出現回数をカウントするので、出現回数が2で割り切れるならば、これは正方形です。

このようにして、2つで割り切れる最も右の要素が最大の正方形である別のシーケンスを得ることができます。

ArrayListで発生をカウントする最も効率的な方法は何ですか？または、最大の広場を見つけるより良い方法はありますか？

Answer 1

ナイーブ（ブルートフォース）溶液：

が所定数未満の正方形のリストを生成し、次いでダウン反復このリストは、エントリが与えられた数を分割するかどうかをチェックします。除数を見つけたらそれを止め、それが答えです。

これを調整して、すべてを一度に見るのではなく、候補リストを生成することもできます。フロア（sqrt（given））から始まり、除数が除数であるものを見つけるまで、減分します。

より多くのあなたの計画に似た何か：

ファクター数、および素因数や要因としての多重度のマップを構築します。

マップを通過し、すべての奇数multiplicitesを1つ減らします。

調整された多重度にマップのすべての数値を掛けます。

Answer 2

自然数にアルゴリズムを使用する義務はありますか？

数字の平方根を取って切り捨てることはできませんか？

すなわちTRUNC（平方根（10001））= 100 =最大正方形

Answer 3

これを行うためにアレイを構築する必要はありません。あなたが行くようにあなたがちょうどこの擬似コード（別名パイソン）のように、四角形を構築することができます。

from math import sqrt 

def sqrfact(n): 
    lim = sqrt(n) + 1 
    x = 2 
    while x <= lim: 
     if n % x == 0: 
      p = n/x 
      if p % x == 0: 
       return (x ** 2) * sqrfact(p/x) 
      else: 
       return sqrfact(p) 
     x += 1 

    # No factors. 
    return 1 

番号、あなたの入力の種類によっては、これは、ブルートフォースより少し速いかもしれません。