Ich arbeite an Problem 12 bezüglich der ersten Dreieckszahl mit 500 Teilern. Ich habe versucht, die Lösung brutal zu erzwingen. Ich bekomme 300 Teiler in ungefähr 35 Sekunden und kann innerhalb von 10 Minuten nicht 400 bekommen. Ich werde meine Lösung ändern, um die Primfaktor-Methode zu verwenden, aber ich habe jetzt gesehen, dass die Leute diese Lösung immer noch mit roher Gewalt in weniger als einer Minute bekommen.
Könnten Sie bitte meinen Code kritisieren und mir sagen, ob ich etwas verpasse, das das fürchterlich ineffizient macht?
%Vor%Update: Verstanden, danke. Geändert, um nur die Quadratwurzel der Zahl zu überprüfen, und eine zusätzliche Überprüfung durchgeführt, um zu sehen, ob es ein perfektes Quadrat war. So konnte ich das Set komplett entfernen. 500 Divisoren liefen in 12 Sekunden.
Sie suchen derzeit nach Divisoren bis zu dividend/2 . Sie können dies auf sqrt(dividend) reduzieren, was asymptotisch schneller ist. Ein spezieller Fall kann erforderlich sein, wenn dividend quadratisch ist.
Mein C ++ - Code für Problem 12 (der im Wesentlichen dasselbe wie Ihr verwendet, aber dieses untere Limit verwendet und auch nur Divisoren zählt, anstatt sie im Set zu speichern) dauert etwa 1 Sekunde.
Ich sehe, dass Sie versucht haben, dies zu optimieren, indem Sie Ihre Schleife auf dividend/2 beschränken, anstatt den ganzen Weg bis zu dividend zu durchlaufen. Dich auf sqrt(dividend) zu beschränken, wäre besser (in dem Sinne, dass du weniger Teiler kontrollierst).
Außerdem müssen Sie, wenn Sie sich durch die Quadratwurzel der Dividende begrenzen, nicht nach doppelten Divisoren suchen. Das wird nur für quadratische Zahlen passieren, also überprüfe einfach, ob index == dividende / index, um eine doppelte Einfügung zu vermeiden.
Ich bin mir nicht sicher, warum Sie die Typvariable divisors , eine set in der NumOfDivisors-Methode benötigen. Warum ist das Zählen von numDivisors (mit Index bis sqrt( dividend ) ) nicht ausreichend? ( set wird als ausgeglichener binärer Suchbaum implementiert, es verlangsamt die Methode.). Darüber hinaus scheint es, dass Sie divisors.insert( .. ) zweimal aufrufen.
Tags und Links c++