C# - Teiler durch Primzahlfaktorisierung finden

  • C#
  • .NET (FX) 4.5–4.8

Es gibt 18 Antworten in diesem Thema. Der letzte Beitrag () ist von exc-jdbi.

    C# - Teiler durch Primzahlfaktorisierung finden

    Hey,

    Ich möchte so effizient wie möglich alle Teiler eines gegebenen int finden. (Eventuell mit dem Hintergedanken das später auf long zu erweitern).
    Es gibt verschiedene Möglichkeiten dieses Problem zu lösen.
    Um das ganze jedoch so performant und effizient wie möglich zu machen, war die Idee zuvor Primzahlen auszuschließen.
    Man muss natürlich sagen der Begriff "effizient" ist hier nur relativ, da Primzahlfaktorisierung zu den NP-Vollständigen Problem gezählt wird.

    Ich habe im Internet rechercheirt und ein Python Skript gefunden das ziemlich schnell alle Teiler einer Zahl findet.
    Dieses Skript habe ich versucht soweit es mir möglich war in C# umzuschreiben.

    Original Python Code:

    C#-Quellcode

    1. from itertools import compress
    2. def primes(n):
    3. """ Returns a list of primes < n for n > 2 """
    4. sieve = bytearray([True]) * (n//2)
    5. for i in range(3,int(n**0.5)+1,2):
    6. if sieve[i//2]:
    7. sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
    8. return [2,*compress(range(3,n,2), sieve[1:])]
    9. def factorization(n):
    10. """ Returns a list of the prime factorization of n """
    11. pf = []
    12. for p in primeslist:
    13. if p*p > n : break
    14. count = 0
    15. while not n % p:
    16. n //= p
    17. count += 1
    18. if count > 0: pf.append((p, count))
    19. if n > 1: pf.append((n, 1))
    20. return pf
    21. def divisors(n):
    22. """ Returns an unsorted list of the divisors of n """
    23. divs = [1]
    24. for p, e in factorization(n):
    25. divs += [x*p**k for k in range(1,e+1) for x in divs]
    26. return divs
    27. n = 2147483646
    28. primeslist = primes(int(n**0.5)+1)
    29. print(divisors(n))


    Die Primezahl funktion def primes(n) habe ich nicht ganz verstanden.
    Daher habe ich diesen Schritt vorerst mal durch ein Sieb des Eratosthenes ersetzt was (in meinem Fall) irgendwie ziemlich langsam ist.

    Mein C# Code:

    C#-Quellcode

    1. public class DivisorFinder
    2. {
    3. private int _number;
    4. public DivisorFinder(int number)
    5. {
    6. _number = number;
    7. }
    8. private IEnumerable<int> FindPrimes(int upperLimit)
    9. {
    10. var composite = new BitArray(upperLimit);
    11. var sqrt = (int) Math.Sqrt(upperLimit);
    12. for (int p = 2; p < sqrt; ++p)
    13. {
    14. if (composite[p])
    15. continue;
    16. yield return p;
    17. for (int i = p * p; i < upperLimit; i += p)
    18. composite[i] = true;
    19. }
    20. for (int p = sqrt; p < upperLimit; ++p)
    21. if (!composite[p])
    22. yield return p;
    23. }
    24. private IEnumerable<(int, int)> FindPrimeFactors(IEnumerable<int> primesList)
    25. {
    26. var factors = new List<(int, int)>();
    27. foreach (var prime in primesList)
    28. {
    29. if (prime * prime > _number)
    30. break;
    31. int count = 0;
    32. while (_number % prime == 0)
    33. {
    34. _number = _number / prime;
    35. count++;
    36. }
    37. if (count > 0)
    38. factors.Add((prime, count));
    39. }
    40. if (_number > 1)
    41. factors.Add((_number, 1));
    42. return factors;
    43. }
    44. public IEnumerable<int> FindDivisors()
    45. {
    46. var primes = FindPrimes((int) (Math.Pow(_number, 0.5) + 1));
    47. var factors = FindPrimeFactors(primes);
    48. var divisors = new HashSet<int> {1};
    49. foreach (var factor in factors)
    50. {
    51. var stuff = new HashSet<int>();
    52. for (int i = 0; i < factor.Item2 + 1; i++)
    53. {
    54. foreach (int x in divisors)
    55. {
    56. stuff.Add((int) Math.Pow(x * factor.Item1, i));
    57. }
    58. }
    59. divisors.UnionWith(stuff);
    60. }
    61. Console.WriteLine($"Found {divisors.Count()} divisors.");
    62. return divisors;
    63. }
    64. }


    Die Klasse lässt sich wie folgt verwenden:

    C#-Quellcode

    1. private static void Main()
    2. {
    3. var number = 2147483637;
    4. var stopWatch = new Stopwatch();
    5. var divisorFinder = new DivisorFinder(number);
    6. Console.WriteLine($"Target value: {number}");
    7. stopWatch.Start();
    8. var divisors = divisorFinder.FindDivisors();
    9. stopWatch.Stop();
    10. var timeSpan = stopWatch.Elapsed;
    11. Console.WriteLine(string.Join(", ", divisors));
    12. Console.WriteLine($"Completed after {timeSpan.Seconds}:{timeSpan.Milliseconds}");
    13. Console.ReadKey();
    14. }


    Beispielsweise, für 2147483637 bekomme ich folgendes Ergebnis, welches auch korrekt ist:

    C#-Quellcode

    1. [1, 3, 9, 27, 13, 39, 117, 351, 6118187, 18354561, 55063683, 165191049, 79536431, 238609293, 715827879, 2147483637]


    Das Problem ist mein Code benötigt dafür ~18 Sekunden, das Python Skript nur wenige Millisekunden.
    Wie kann ich meinen Code optimieren und wie bekomme ich die python-prime Funktion in C# umgeschrieben?
    Zusätzlich stelle ich mir die Frage ob sich das ganze später noch weiter verbessern lässt indem bereits gefundene Primzahlen gecached werden und nicht neu generiert werden müssen ö.Ä?
    Aber zuerst mal geht es darum das ganze an sich nahe an die Laufzeit des Pythonskripts zu bekommen.
    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von „Rikudo“ ()

    Rikudo schrieb:

    for i in range(3,int(n**0.5)+1,2):

    Rikudo schrieb:

    for (int p = 2; p < sqrt; ++p)
    Da sehe ich doch schon einen wesentlichen Unterschied, den Du selbst erkennen müsstest: for (int p = 3; p < sqrt; p += 2)
    Ich habe keine Ahnung von Python. Gehe ich Recht in der Annahme, dass // Integer-Division bedeutet?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    @RodFromGermany In Python ist // die Flooring Division also bspw:
    4.0 // 1.5 ergibt 2.0

    Das Ändern des Loops beschleunigt ein bisschen, von 19s auf 16s, also scheinbar ist irgend etwas anderes die Große Bremse.
    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Rikudo“ ()

    @RodFromGermany sieve ist einfach nur eine Variable.
    Ich habe den Code nochmal ein bisschen verbessert, da die Primzahlfunktion mehrfach invoked wurde.
    Das Hauptproblem in der Geschwindigkeit scheint meine FindPrimeFactors Funktion zu sein.

    Und zu deiner Anmerkung in Post #2, das ist falsch, ich muss schon for(int p = 2; p < sqrt; ++p) verwenden.
    Würde ich es so machen wie du gesagt hast lasse ich Zahlen die auch Teiler sein können.

    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Rikudo“ ()

    Habs (mehr oder weniger)
    Irgendetwas stimmt noch nicht ganz. Manchmal schleichen sich falsche Teiler ein.
    Bspw für den Input 18 bekomme ich:


    Das passt nicht, 36 ist kein gültiger Teiler. Ebenso bekomme ich falsche Werte für manche höheren Zahlen wie 50, 90 etc

    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Rikudo“ ()

    @Rikudo Ich hatte das (...,2) als Step 2 (+= 2) interpretiert, das sollte aber auf einer Phyton-Syntax-Seite ordentlich beschrieben sein.
    Poste mal den Code, vielleicht sehe ich noch was.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    @RodFromGermany

    C#-Quellcode

    1. public class DivisorFinder
    2. {
    3. /// <summary>
    4. /// The number that is searched for divisors
    5. /// </summary>
    6. private int _number;
    7. /// <summary>
    8. /// Search new divisors for a given integer
    9. /// </summary>
    10. /// <param name="number">Integer that is searched for divisors</param>
    11. public DivisorFinder(int number)
    12. {
    13. _number = number;
    14. }
    15. /// <summary>
    16. /// Find prime numbers up to a given maximum
    17. /// </summary>
    18. /// <param name="upperLimit">The upper limit</param>
    19. /// <returns>All prime numbers between 2 and upperLimit</returns>
    20. private IEnumerable<int> FindPrimes(int upperLimit)
    21. {
    22. var composite = new BitArray(upperLimit);
    23. var sqrt = (int) Math.Sqrt(upperLimit);
    24. for (int p = 2; p < sqrt; ++p)
    25. {
    26. if (composite[p])
    27. continue;
    28. yield return p;
    29. for (int i = p * p; i < upperLimit; i += p)
    30. composite[i] = true;
    31. }
    32. for (int p = sqrt; p < upperLimit; ++p)
    33. if (!composite[p])
    34. yield return p;
    35. }
    36. /// <summary>
    37. /// Search prime factors in a given IEnumerable of prime numbers
    38. /// </summary>
    39. /// <param name="primesList">The IEnumerable of previously calculated prime numbers</param>
    40. /// <returns>IEnumerable of prime factors</returns>
    41. private IEnumerable<(int, int)> FindPrimeFactors(IEnumerable<int> primesList)
    42. {
    43. foreach (var prime in primesList)
    44. {
    45. if (prime * prime > _number)
    46. break;
    47. int count = 0;
    48. while (_number % prime == 0)
    49. {
    50. _number = _number / prime;
    51. count++;
    52. }
    53. if (count > 0)
    54. yield return ((prime, count));
    55. }
    56. if (_number > 1)
    57. yield return (_number, 1);
    58. }
    59. /// <summary>
    60. /// Find all divisors of the target number
    61. /// </summary>
    62. /// <returns>IEnumerable of integers that divide the target without reminder</returns>
    63. public IEnumerable<int> FindDivisors()
    64. {
    65. // var primes = FindPrimes((int) (Math.Sqrt(_number) + 1));
    66. var primes = FindPrimes((int) (Math.Sqrt(_number) + 1));
    67. var factors = FindPrimeFactors(primes);
    68. var divisors = new HashSet<int> {1};
    69. foreach (var factor in factors)
    70. {
    71. var set = new HashSet<int>();
    72. for (int i = 0; i < factor.Item2 + 1; i++)
    73. {
    74. foreach (int x in divisors)
    75. {
    76. set.Add((int) Math.Pow(x * factor.Item1, i));
    77. }
    78. }
    79. divisors.UnionWith(set);
    80. }
    81. return divisors;
    82. }
    83. }


    Ich konnte noch nicht herrausfinden was für den Bug verantwortlich ist.
    Ich gehe davon aus es liegt entweder an der FindPrimeFactors oder an der FindDivisors Funktion.
    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Rikudo“ ()

    Hallo @Rikudo

    Ich vermute mal, dass Zeile 87 bei der letzten Zahl einen Overflow verursacht (n = 2147483646). Der letzte Divisor ist sowieso 2147483646.
    Zwischen Zeile 84 und 85 könnte man doch so was noch reinschreiben, habs aber nicht getestet.

    C#-Quellcode

    1. if (i == 0) { set.Add(1); continue; }



    Freundliche Grüsse

    exc-jdbi
    @Rikudo Habs leider (noch) nicht getestet.
    Wenn das tatsächlich ein Overflow ist, kannst Du durch Umschwenken von int auf long einen größeren "Arbeitsbereich" erzeugen, und bei einem 64-Bit-Prozessor dürfte sich das praktisch nicht auf die Laufzeit auswirken.
    Ich denke mal, wenn Du die Zeile

    C#-Quellcode

    1. set.Add((int) Math.Pow(x * factor.Item1, i));
    ordentlich umbaust, wird das ganze deutlich schneller.
    Tausche die beiden inneren Schleifen (i innerhalb von x) und mach aus der Potenzierung eine Multiplikation.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Hallo @Rikudo

    Versuchs mal probehalber so (ungetestet):
    Sollte das funktionieren, kann man sich gedanken machen, wie man die Routine optimiert. Den Vorschlag von RFG würde ich auch in betracht ziehen.

    C#-Quellcode

    1. private bool IsOverflow(long i1, long i2)
    2. {
    3. long l = i1 * i2;
    4. long ma = Int32.MaxValue,mi = Int32.MinValue;
    5. if (l >= mi && l <= ma) return true;
    6. return false;
    7. }
    8. public IEnumerable<Int32> FindDivisors()
    9. {
    10. var num = _number;
    11. var n = (int)(Math.Sqrt(_number) + 1);
    12. var primes = FindPrimes(n);
    13. var factors = FindPrimeFactors(primes);
    14. var divisors = new HashSet<int> { 1 };
    15. foreach (var factor in factors)
    16. {
    17. var set = new HashSet<int>();
    18. for (int i = 0; i < factor.Item2 + 1; i++)
    19. {
    20. if (i == 0) { set.Add(1); continue; }
    21. foreach (int x in divisors)
    22. {
    23. if (IsOverflow(x, factor.Item1))
    24. {
    25. //int t = (int)Math.Pow(x * factor.Item1, i);
    26. int t = (int)(x*Math.Pow(factor.Item1, i));
    27. set.Add(t);
    28. }
    29. else
    30. {
    31. set.Add(num); continue;
    32. }
    33. }
    34. }
    35. divisors.UnionWith(set);
    36. }
    37. return divisors.OrderBy(x => x).ToList();
    38. }


    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „exc-jdbi“ ()

    @exc-jdbi
    @RodFromGermany
    Danke für eure Antworten. Es lag daran das ich die Primzahlen bis n generiert habe.
    Dabei hat es ja gelangt nur bis (int) Math.Pow(n, 0.5) + 1 zu gehen.
    Jetzt ist das ganze schon mal um einiges schneller. Aber nach wie vor noch nicht maximal optimiert.
    Alle Teiler für die Zahlen von 1 bis 1.000.000 zu finden hat ~10.2 Sekunden gedauert.

    Ich habe noch zwei Ideen wie man eventuell noch einiges an Performance rausholen könnte.

    1) Prime/Primefaktor Caching
    Zur Zeit werden für jede Zahl die Primzahlen neu gesucht.
    Ich hatte die Idee das, eine Variable dazu genutzt wird die höchste Zahl zu speichern.
    Wird eine höhere Zahl zu der die Primfaktoren gefunden werden sollen and die Funktion gegeben, wird nur von der höchsten, bereits gecached Primzahl weiter gesucht bis zu dem Limit von (int) Math.Pow(n, 0.5) + 1 zu gehen.
    Ist die Zahl kleiner, so könnten die Gecachten Primzahlen verwendet werden und es müssen keine neuen gesucht werden.
    Eventuell geht etwas ähnliches für die Faktoren. Was meint Ihr, würde das einen Performancevorteil bringen?
    Ich habe leider kein Plan wie ich das effizient implementieren soll, insbesondere da ich mit Arrays fester größe Arbeite.
    Eventuell kann jemand mir ein Beispiel zeigen.

    2) Doppelte HashSets
    In der FindDivisors Funktion habe ich zwei HashSets die mit jedem Schleifendurchlauf kombiniert werden.
    Kann man das eventuell auch nur mit einem HashSet lösen?

    Hier ist mein Aktueller Code:

    C#-Quellcode

    1. public static class DivisorFinder
    2. {
    3. private static IEnumerable<int> FindPrimes(int upperLimit)
    4. {
    5. var composite = new BitArray(upperLimit);
    6. var sqrt = (int) Math.Sqrt(upperLimit) + 1;
    7. if (sqrt >= 2) yield return 2;
    8. for (var i = 4; i < upperLimit && i > 0; i += 2)
    9. composite[i] = true;
    10. for (var p = 3; p < sqrt; p += 2) {
    11. if (composite[p]) continue;
    12. yield return p;
    13. for (var i = p * p; i < upperLimit && i > 0; i += p)
    14. composite[i] = true;
    15. }
    16. if (sqrt % 2 == 0) sqrt++;
    17. for (var p = sqrt; p < upperLimit; p += 2)
    18. if (!composite[p])
    19. yield return p;
    20. }
    21. private static IEnumerable<int> FindPrimeFactors(IEnumerable<int> primesList, int number)
    22. {
    23. var upperLimit = (int) Math.Sqrt(number) + 1;
    24. foreach (var prime in primesList) {
    25. if (prime > upperLimit)
    26. break;
    27. while (number % prime == 0) {
    28. number = number / prime;
    29. yield return prime;
    30. upperLimit = (int) Math.Sqrt(number) + 1;
    31. }
    32. }
    33. if (number > 1)
    34. yield return number;
    35. }
    36. public static IEnumerable<int> FindDivisors(int number)
    37. {
    38. var primes = FindPrimes((int) Math.Pow(number, 0.5) + 1);
    39. var factors = FindPrimeFactors(primes, number);
    40. var divisors = new HashSet<int> {1};
    41. foreach (var factor in factors) {
    42. var set = new HashSet<int>();
    43. foreach (var x in divisors)
    44. set.Add(x * factor);
    45. divisors.UnionWith(set);
    46. }
    47. return divisors.OrderBy(d => d);
    48. }
    49. }


    Bin gespannt auf eure Vorschläge.
    C# Developer
    Learning C++
    Hallo @Rikudo

    Ich habs jetzt kurz von dir kopiert, und musste zwecks meinem Dinosaurier-System Anpassungen machen.
    Meine Variante besitzt z.B. keine Return-Tubel.

    Deine 10s finde ich erschreckend.

    Zeiten:
    int.maxvalue-1 >> ~23ms
    1'000'000 >> ~20ms

    Spoiler anzeigen

    C#-Quellcode

    1. using System;
    2. using System.Linq;
    3. using System.Text;
    4. using System.Collections;
    5. using System.Diagnostics;
    6. using System.Collections.Generic;
    7. namespace DivisionFinderCs
    8. {
    9. class Divisors32
    10. {
    11. static void Main(string[] args)
    12. {
    13. var sw=new Stopwatch ();
    14. int n = 1000000;// int.MaxValue - 1;
    15. DivisorFinder df = new DivisorFinder(n);
    16. sw.Restart();
    17. var res = df.FindDivisors();
    18. sw.Stop();
    19. Console.WriteLine(sw.ElapsedMilliseconds);
    20. Console.ReadLine();
    21. }
    22. }
    23. }
    24. public class DivisorFinder
    25. {
    26. private int _number;
    27. public DivisorFinder(int number)
    28. {
    29. _number = number;
    30. }
    31. private IEnumerable<int> FindPrimes(int upperLimit)
    32. {
    33. var composite = new BitArray(upperLimit);
    34. var sqrt = (int) Math.Sqrt(upperLimit);
    35. for (int p = 2; p < sqrt; ++p)
    36. {
    37. if (composite[p])
    38. continue;
    39. yield return p;
    40. for (int i = p * p; i < upperLimit; i += p)
    41. composite[i] = true;
    42. }
    43. for (int p = sqrt; p < upperLimit; ++p)
    44. if (!composite[p])
    45. yield return p;
    46. }
    47. private IEnumerable<int[]> FindPrimeFactors(IEnumerable<int> primesList)
    48. {
    49. foreach (var prime in primesList)
    50. {
    51. if (prime * prime > _number)
    52. break;
    53. int count = 0;
    54. while (_number % prime == 0)
    55. {
    56. _number /= prime;
    57. count++;
    58. }
    59. if (count > 0)
    60. yield return new int[] {prime, count};
    61. }
    62. if (_number > 1)
    63. yield return new int[] {_number, 1};
    64. }
    65. public IEnumerable<Int32> FindDivisors()
    66. {
    67. var num = _number;
    68. var n = (int)(Math.Sqrt(_number) + 1);
    69. var primes = FindPrimes(n);
    70. var factors = FindPrimeFactors(primes);
    71. var divisors = new HashSet<int> { 1 };
    72. foreach (var factor in factors)
    73. {
    74. var set = new HashSet<int>();
    75. for (int i = 0; i < factor[1] + 1; i++)
    76. {
    77. if (i == 0) { set.Add(1); continue; }
    78. foreach (int x in divisors)
    79. {
    80. int t = (int)(x * Math.Pow(factor[0], i));
    81. set.Add(t);
    82. }
    83. }
    84. divisors.UnionWith(set);
    85. }
    86. return divisors.OrderBy(x => x).ToList();
    87. }
    88. }



    Freundliche Grüsse

    exc-jdbi

    exc-jdbi schrieb:

    int t = (int)(x * Math.Pow(factor[0], i));
    Wenn Du die Schleifen tauschst, kannst Du die Potenzierung durch eine Multiplikation erwetzen, siehe Post #11.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    @exc-jdbi Du hast mich falsch verstanden :D
    Mein Code braucht 10 Sekunden für alle Zahlen von 1-1.000.000.
    Also eine Schleife von 1-1.000.000 und für jede Zahl wurden die Teiler berechnet.
    Ich werde jetzt mal deine Änderung benchmarken.

    Edit: Für int.MaxValue benötigt meine Klasse 10ms im Vergleich zu den 23ms von deinem Ansatz.
    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Rikudo“ ()

    Kein einfaches Sache.

    Ich nehme an, du willst auf der yield-Variante bleiben. Ich hab noch zu wenig Übung mit diesen yield's. Bin mir aber sicher, dass es eine Möglichkeit gibt.

    Ich hätte das so gemacht, dass ich alle Primzahlen der höchsten Zahl in einem Array festhalte, und dann von so weg eine Möglichkeit suche, die Faktorisierung umzusetzen.

    Freundliche Grüsse

    exc-jdbi