11

だから私は単に与えられた数のすべての除数を見つけたいのです（数自体を除いて）。現在、私はこれを持っています：

public static List<int> proper_divisors(int x)
{
    List<int> toreturn = new List<int>();
    toreturn.Add(1);
    int i = 0;
    int j=1;
    int z = 0;
    while (primes.ElementAt(i) < Math.Sqrt(x))
    {
        if (x % primes.ElementAt(i) == 0)
        {
            toreturn.Add(primes.ElementAt(i));
            toreturn.Add(x / primes.ElementAt(i));
            j = 2;
            z = (int)Math.Pow(primes.ElementAt(i), 2);
            while (z < x)
            {
                if (x % z == 0)
                {
                    toreturn.Add(z);
                    toreturn.Add(x / z);
                    j++;
                    z = (int)Math.Pow(primes.ElementAt(i), j);
                }
                else
                {
                    z = x;
                }
            }
        }
        i++;
    }
    toreturn = toreturn.Distinct().ToList<int>();
    return toreturn;
}

ここで、primesは素数のリストです（正しく、十分に大きいと仮定します）。このアルゴリズムは、すべての素因数を検出するという意味で機能しますが、すべての素因数を検出するわけではありません（つまり、34534を指定すると、{1,2,17267,31,1114}を返しますが、62は組み合わせであるため、{62、557}を見逃します。したがって、557も見逃します。

また、数の素因数を取得しようとしましたが、それをすべての正しい組み合わせのリストに変換する方法がわかりません。

そのアルゴリズムのコードは次のとおりです。

public static List<int> prime_factors(int x)
{
    List<int> toreturn = new List<int>();
    int i = 0;
    while (primes.ElementAt(i) <= x)
    {
        if (x % primes.ElementAt(i) == 0)
        {
            toreturn.Add(primes.ElementAt(i));
            x = x / primes.ElementAt(i);
        }
        else
        {
            i++;
        }
    }
    return toreturn;
}

最初のものを修正する方法、または2番目のものから組み合わせのリストを作成する方法についてのアイデアはありますか（私はそれがより速いのでそれを好むでしょう）？

4

2 に答える 2

8

あなたはすでに素因数のリストを持っているので、あなたがしたいのはそのリストのべき集合を計算することです。

ここで、1つの問題は、リストに重複がある可能性があることです（たとえば、20 = 2 * 2 * 5の素因数）が、セットは重複を許可しません。したがって、リストの各要素を{x、y}の形式の構造に射影することで一意にすることができます。ここで、xは素数、yはリスト内の素数のインデックスです。

var all_primes = primes.Select((x, y) => new { x, y }).ToList();

ここで、all_primesは{x、y}の形式のリストです。ここで、xは素数、yはリスト内のインデックスです。

次に、べき集合（GetPowerSet以下の定義）を計算します。

var power_set_primes = GetPowerSet(all_primes);

したがって、power_set_primesは匿名型IEnumerable<IEnumerable<T>>であり、xとyは型です。T{x, y}int

次に、べき集合の各要素の積を計算します

foreach (var p in power_set_primes)
{
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y);
    factors.Add(factor);
}

すべてを一緒に入れて：

var all_primes = primes.Select((x, y) => new { x, y }).ToList(); //assuming that primes contains duplicates.
var power_set_primes = GetPowerSet(all_primes);
var factors = new HashSet<int>();

foreach (var p in power_set_primes)
{
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y);
    factors.Add(factor);
}

べき集合の実装については、http： //rosettacode.org/wiki/Power_Setから。

public 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];
}
于 2011-04-26T16:28:38.710 に答える
5

以前にも同様の質問がありましたが、これにはIEnumerableを使用した興味深い解決策があります。因子ではなくすべての除数が必要で、少なくともC＃3.0を使用していると仮定すると、次のようなものを使用できます。

static IEnumerable<int> GetDivisors(int n)
{
    return from a in Enumerable.Range(2, n / 2)
           where n % a == 0
           select a;                      
}

次に、次のように使用します。

foreach(var divisor in GetDivisors(10))
    Console.WriteLine(divisor);

または、リストが必要な場合は、次のようにします。

List<int> divisors = GetDivisors(10).ToList();
于 2011-04-26T16:35:55.263 に答える