Primzahlen - Geschwindigkeit
-
Hi,
warum ist der erste Code bei großen Zahlen deutlich schneller als der zweite?
Beim ersten werden ja bei "for (unsigned j = 1; j < i; ++j)" immer alle Zahlen bis i geprüft, beim zweiten wird nur so oft geprüft wie schon Primzahlen im vector stehen - was deutlich weniger Überprüfungen sein müssten.Mal davon abgesehen das es sicher keine gute Methode ist um Primzahlen zu finden müsste doch das zweite Programm schneller sein da es weniger Werte prüft.
vector<int> checkForPrim(unsigned max) { vector<int>primeList; unsigned count = 0; for (unsigned i = 2; i < max; ++i) { for (unsigned j = 1; j < i; ++j) { if (i % j == 0) ++count; } if (count < 2) primeList.push_back(i); count = 0; } return primeList; }
vector<int> checkForPrim(unsigned max) { vector<int>primeList(1); primeList[0] = 2; unsigned count = 0; for (unsigned i = 2; i < max; ++i) { for (unsigned j = 0; j < primeList.size(); ++j) { if (i % primeList[j] == 0) ++count; } if (count < 1) primeList.push_back(i); count = 0; } return primeList; }
-
Optimierungen
optimiertaktiviert? Sonst erübrigt sich das.
-
Der zweite Code sieht falsch aus. Da du mit 1 als Teiler anfängst, ist count am Ende in jedem Fall >= 1, also werden überhaupt keine Primzahlen gefunden.
-
Funktioniert schon, der erste Teiler ist 2 und beide Funktionen geben das gleiche aus. Der zweite Code ist nur deutlich langsamer obwohl die zweite Schleife weniger durchlaufen wird.
-
Nathan schrieb:
Optimierungen optimiert? Sonst erübrigt sich das.
Edit: Lol, aktiviert nicht optimiert
-
Ah alles klar
Weiß zwar nicht wo ich die direkt Aktivieren kann aber wenn ich von debug auf release wechsle ist es in 3 Sekunden statt x Minuten fertig Danke für den Hinweis.
-
dentho schrieb:
Funktioniert schon, der erste Teiler ist 2 und beide Funktionen geben das gleiche aus. Der zweite Code ist nur deutlich langsamer obwohl die zweite Schleife weniger durchlaufen wird.
Ah, nvm.
Hatte dasvector<int>primeList(1); primeList[0] = 2;
als
vector<int>primeList{1};
gelesen. Diese Initialisierung ist verwirrend weil unnötig.