Suchergebnisse

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 recherche…

@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.

@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.

Habs (mehr oder weniger) Irgendetwas stimmt noch nicht ganz. Manchmal schleichen sich falsche Teiler ein. Bspw für den Input 18 bekomme ich: wQzZog8.png Das passt nicht, 36 ist kein gültiger Teiler. Ebenso bekomme ich falsche Werte für manche höheren Zahlen wie 50, 90 etc

@RodFromGermany C#-Quellcode (95 Zeilen) 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.

@RodFromGermany Und eine Idee wo der Bug entsteht? Ich konnte es irgendwie nicht ermitteln. Die Primzahlfunktion scheint aber soweit intakt, zumindest als ich gedebugged habe waren alle Werte korrekt.

@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…

@exc-jdbi Du hast mich falsch verstanden 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.

Haha Hast du eventuell eine Idee wie man zuvor generierte Werte cachen könnte, und nur die "fehlenden" Primes generiert?