2

タイトルが不明確で申し訳ありませんが、適切に述べる方法がわからないので（自由に編集してください）、例を挙げます。

sqrt(108) ~ 10.39... しかし、この sqrt(108)=6*sqrt(3) のようにしたいので、2つの数値に展開することを意味します

それが私のアルゴリズムです

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 を使用します。もちろん、適切な構文を使用します。

4

3 に答える 3

3

これには高速なアルゴリズムはありません。すべての二乗係数を見つける必要があります。これには、少なくともある程度の因数分解が必要です。

ただし、アプローチをかなり高速化できます。まず、n の立方根までの素因数を見つけるだけでよく、整数の平方根が整数であるかどうかを判断するための最速の方法のアドバイスを使用して、n 自体が完全平方かどうかをテストします。

次に速度を上げて、一番下の要因から作業を進めます。素因数を見つけるたびに、n をその素因数で繰り返し割り、平方を累積します。n のサイズを小さくすると、到達する制限も小さくなります。これにより、ほとんどの数がいくつかの小さな数で割り切れるという事実を利用できます。これにより、因数分解するために残っている数のサイズがすぐに縮小され、検索をすぐに終了できます。

次のパフォーマンスの改善は、どの数字で試行分割を行うかについてより賢くなり始めます。たとえば、特殊なケース 2 では、奇数のみをテストします。アルゴリズムの速度が再び 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-18T16:57:00.207 に答える
2

このための高速アルゴリズムがある可能性は低いです。https://mathoverflow.net/questions/16098/complexity-of-testing-integer-square-freeness、特にhttps://mathoverflow.net/questions/16098/complexity-of-testing-integer-square-freeness/16100を参照してください＃16100

于 2011-02-18T16:15:54.237 に答える
0
  1. すべての素数除数を昇順でリストします（例：2700 = 2 * 2 * 3 * 3 * 3 * 5 * 5）。これは最も遅いステップであり、sqrt（N）操作が必要です。
  2. アキュムレータを作成します（1から開始）。このリストをスキャンします。数値のペアごとに、アキュムレータにそれら（の1つ）を掛けます。したがって、上記のリストをスキャンすると、2 * 3*5になります。
  3. アキュムレータは乗数です。残りは平方根の下に残ります。
于 2011-02-18T16:30:13.607 に答える