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.


  • Mod

    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.


  • Mod

    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 das

    vector<int>primeList(1);
        primeList[0] = 2;
    

    als

    vector<int>primeList{1};
    

    gelesen. Diese Initialisierung ist verwirrend weil unnötig.


Log in to reply