1

この興味深いアルゴリズムをできる限り改善しようとしています。

今のところ、私はこれを持っています：

using System;

class Program
{

    static void Main()
    {
        ulong num, largest_pFact;
        uint i = 2;
        string strNum;

        Console.Write("Enter number: ");
        strNum = Console.ReadLine();
        num = ulong.Parse(strNum);
        largest_pFact = num;


        while (i < Math.Sqrt((double) largest_pFact))
        {
            if (i % 2 != 0 | i == 2) {
                if (largest_pFact % i == 0) 
                    largest_pFact /= i;
            }

            i++;
        }

        Console.WriteLine("Largest prime factor of {0} is: {1}", num, largest_pFact);
        Console.ReadLine();

    }
}

アイデアはありますか？

ありがとう！

EDIT：Benのアルゴリズムを実装しました。助けてくれてありがとう！

4

6 に答える 6

2

私はより高速なアルゴリズムをここに持っています。

平方根を排除し、繰り返される要素を正しく処理します。

さらに最適化:

static private ulong maxfactor (ulong n)
{
    unchecked
    {
        while (n > 3 && 0 == (n & 1)) n >>= 1;

        uint k = 3;
        ulong k2 = 9;
        ulong delta = 16;
        while (k2 <= n)
        {
            if (n % k == 0)
            {
                n /= k;
            }
            else
            {
                k += 2;
                if (k2 + delta < delta) return n;
                k2 += delta;
                delta += 8;
            }
        }
    }

    return n;
}

これが実際のデモです: http://ideone.com/SIcIL

于 2011-02-10T00:08:35.597 に答える
1

まず、特別なケース 2 をループの外に移動します。一度処理できる場合、ループ全体でそれをチェックしても意味がありません。可能であれば、intではなくデータ型を使用してuintください。一般に高速です。

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
while (i < Math.Sqrt((double) largest_pFact)) {
  if (i % 2 != 0) {
    if (largest_pFact % i == 0) {
      largest_pFact /= i;
    }
  }
  i++;
}

平方根の計算は比較的コストがかかるため、事前に行う必要があります。

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  if (i % 2 != 0) {
    if (largest_pFact % i == 0) {
      largest_pFact /= i;
    }
  }
  i++;
}

i次に、モジュロ チェックを 1 つ削除するために、2ずつインクリメントします。

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  if (largest_pFact % i == 0) {
    largest_pFact /= i;
  }
  i += 2;
}

機能するには、ループ内のwhile代わりにが必要だと思います。そうしないと、繰り返される要素がスキップされます。if

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  while (largest_pFact % i == 0) {
    largest_pFact /= i;
  }
  i += 2;
}
于 2011-02-10T00:09:50.820 に答える
1

Math.Sqrtまず、反復ごとに実行する必要はありません。

    int root = Math.Sqrt((double) largest_pFact);

    while (i < root)
    {
        if ((i % 2 != 0 | i == 2) && largest_pFact % i == 0) {
            largest_pFact /= i;
            root = Math.Sqrt((double) largest_pFact);
        }

        i++;
    }
于 2011-02-10T00:55:39.753 に答える
1

-Math.Sqrt((double) maximum_pFact) をいくつかの変数、できれば ulong に格納します。これにより、ループを通過するたびに関数を再計算する必要がなくなり、整数比較は浮動小数点比較よりも高速になる場合があります。ただし、比較を <= に変更する必要があります。

- 偶数でループするのは絶対に避けてください。i=2 の特殊なケースを含めるだけで、3 の i から開始し、ループごとに 2 ずつインクリメントします。i=2,3 を特殊なケースとして、i = 6n+1 または 6n-1 のみをテストすることで、さらに先に進むことができます。

于 2011-02-10T00:02:37.953 に答える
0

おもう：

  • num/2までの素数を生成する
  • num次に、素数で割り切れるかどうかを最大から最小にチェックします

より速くなります。

編集 num/2 NOT sqrt

于 2011-02-10T00:03:05.350 に答える
0

num/2 から開始するよりも、sqrt(num) と 2 の間を調べる方が常に高速です。すべての因数ペア (平方根のものを除く) には、sqrt(num) より小さい数値が 1 つあります。

例: 15 の場合、int(sqrt(15))==3 15/3=5 なので、テストを 7 ではなく 3 で開始することにより、「5」係数を見つけました。

于 2011-02-10T00:16:17.907 に答える