숫자의 모든 제수를 효율적으로 찾는 것

Question

그래서 주어진 숫자의 모든 제수를 찾고 싶습니다 (숫자 자체 제외). 현재는,이 있습니다

소수의 목록입니다 소수가 (이 올바른지 가정하고 충분히 큰)

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; 
} 

. 알고리즘은 모든 기본 요소를 찾지 만 모든 요소가 아니라는 의미에서 작동합니다 (예 : 34534, {1,2,17267,31,1114}를 반환하지만 {62, 557}은 62가 조합이므로 때문에뿐만 아니라 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; 
} 

첫 번째 문제를 해결하는 방법에 대한 아이디어 나 secon에서 조합 목록을 만드는 방법 d 하나 (나는 그것이 더 빠를 것이 더 좋아)?

Answer 1

이미 기본 요소 목록이 있으므로 원하는 것은 해당 목록의 powerset을 계산하는 것입니다.

이제 문제는 목록에 중복 항목이있을 수 있다는 것입니다 (예 : 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}의리스트이다.

var power_set_primes = GetPowerSet(all_primes); 

는 따라서 power_set_primes가 T이 X 및 Y는 입력 int의 인 익명 형식 {x, y} 인 IEnumerable<IEnumerable<T>>이다

그렇다면 우리는 파워 세트 (아래 GetPowerSet 정의)를 계산한다. http://rosettacode.org/wiki/Power_Set 가입일

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); 
} 

를 파워 셋의 구현 예를 들어

다음으로, 우리는 전력의 각 요소의 제품 종합하기

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

설정 계산한다.

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]; 
} 

Answer 2

는 IEnumerable을 사용하여 흥미로운 솔루션을 비슷한 질문 before,이 있었다. 요인이 아닌 모든 약수를 원한다면 적어도 C# 3을 사용한다고 가정하십시오.

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

을 다음과 같이 사용 : 0이 같은 것을 사용할 수의

List<int> divisors = GetDivisors(10).ToList();