6

重複の可能性：
数値のすべての除数を効率的に見つける

これは、一般的な「それを行う方法を見つける」よりもはるかに効率の問題ですが、いくつかの奇妙な結果を得た後、誰かが最後の方法がそれほど非効率的である理由を教えてくれるかどうかを確認したいと思います。

方法1：ブルートフォース、最適化なし

    public static List<int> proper_divisors(int x)
    {
        List<int> toreturn = new List<int>();
        for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++)
        {
            if (x % i == 0)
            {
                toreturn.Add(i);
                toreturn.Add(x / i);
            }
        }
        if (toreturn.ElementAt(toreturn.Count() / 2) == toreturn.ElementAt(toreturn.Count() / 2 - 1))
        {
            toreturn.Remove(toreturn.ElementAt(toreturn.Count() / 2));
        }

        return toreturn;
    }

方法2：以前と同じですが、今回はプライムが最初かどうかを確認します（これらの場合は最も時間がかかるため、プライムチェックにミラーラビンを使用します）

        public static List<int> proper_divisors(int x)
    {
        List<int> toreturn = new List<int>();
        if (!isprime(x))
        {
            for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++)
            {
                if (x % i == 0)
                {
                    toreturn.Add(i);
                    toreturn.Add(x / i);
                }
            }
            if (toreturn.ElementAt(toreturn.Count() / 2) == toreturn.ElementAt(toreturn.Count() / 2 - 1))
            {
                toreturn.Remove(toreturn.ElementAt(toreturn.Count() / 2));
            }
        }
        else
        {
            toreturn.Add(1);
            toreturn.Add(x);

        }
        return toreturn;
    }

素因数を見つけるたびに動作する数を減らし、素数のみを試したため、これまでで最も速い方法であると考えられたのは方法3でした（これらは実行時にふるいによって生成され、約34かかりますすべての素数を100万未満にするためのミリ秒）この方法で最後にやらなければならなかったのは、素因数とその力を取り、すべての素数のリストを作成することでした。

方法3：

                public static HashSet<int> prime_factors(int x)
    {
        if (!isprime(x))
        {
            List<int> toreturn = new List<int>();
            int i = 0;
            while (primes[i] <= x)
            {
                if (x % primes[i] == 0)
                {
                    toreturn.Add(primes[i]);
                    x = x / primes[i];
                }
                else
                {
                    i++;
                }
            }
            var power_set_primes = GetPowerSet(toreturn);
            var factors = new HashSet<int>();
            foreach (var p in power_set_primes)
            {
                var factor = p.Select(z => z).Aggregate(1, (z, y) => z * y);
                factors.Add(factor);
            }
            return factors;
        }
        else
        {
            HashSet<int> toreturn = new HashSet<int>();
            toreturn.Add(1);
            toreturn.Add(x);
            return toreturn;
        }
        public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
    {
        return from m in Enumerable.Range(0, 1 << list.Count)
               select
                   from i in Enumerable.Range(0, list.Count)
                   where (m & (1 << i)) != 0
                   select list[i];
    }

最初の百万の数を因数分解するのにかかった時間：方法1：7223ミリ秒方法2：8985ミリ秒（素数チェックは私が推測する小さな数には価値がない）方法3：49423ミリ秒

だから私の質問は2つあります：1）なぜ方法3はとても遅いのですか？2）それをより速くすることができる何かがありますか？余談ですが、素数はリストとして計算され、配列に変換されました。そうすればもっと速くなると思いました。悪い動き？

4

1 に答える 1

0

これが整数因数分解の問題領域です。ここには、よく知られているアルゴリズムがいくつかあります。

http://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms

最適な組み合わせ + プロファイルを選択することをお勧めします。

私の元のコメント:

プロフィール プロフィール プロフィール。また、効率を重視する場合は、列挙子や LINQ を使用しないでください。C で記述し、P/Invoke を使用します。一般に、測定できるかどうかについて質問しないでください。

于 2011-04-28T13:11:40.570 に答える