Anfängerproblemchen mit recht schwieriger Aufgabe



  • minastaros schrieb:

    Das mag zwar funktionieren, war aber nicht die Aufgabe: Berechnung der Primzahlen und die Zerlegung sollen in zwei getrennten Funktionen erfolgen.

    Oh, stimmt.

    minastaros schrieb:

    Und das nicht ohne Grund.

    Doch, ich fürchte, die Bedingung ist völlig ohne Grund. Sowohl bei trial division als auch beim Sieb des Eratosthenes ist ein Vortest auf Primalität der Teiler Zeitverschwendung.

    minastaros schrieb:

    Nach jeder Teilung y=y/i wird i wieder auf 2 gesetzt, auch wenn alle Primfaktoren 2 bereits längst erledigt sind.

    Habs weggemacht.

    minastaros schrieb:

    Es werden auch die Vielfachen von Primzahlen als mögliche Teiler in y%i in Erwägung gezogen, obwohl diese selbst als Primfaktoren nicht in Frage kommen können. Viele unnötige Divisionen.

    Nicht wirklich.

    void primzer (int y)
    {
    
        int i=1;
    
        while (y > 1)
        {
    
            do
            {
                i = i + 1;
            }while (!primtest(i));
    
            while(y%i==0)
            {
                std::cout<<i<<" "<<y<<"\n";
                y = y/i;
            }
        }
    }
    //Der Code riecht nicht hübsch. Irgendwas stimmt daran nicht.
    


  • Erstmal vielen Dank für die zahlreichen Antworten.

    Also die Eingabe habe ich nun so gefixt:

    // >Eingabe
    int eingabe (void) {
      int x = 0;
      std::cout<<"Bitte geben sie eine natuerliche Zahl ein: "<<std::endl;
      std::cin>>x;
      while (x<1) {
        std::cout<<"Die eingegebene Zahl ist nicht natuerlich!\nBitte geben sie erneut eine natuerliche Zahl ein: "<<std::endl;
        std::cin>>x;
      }
      return x;
    }
    
    //in der main so:
    n = eingabe();
    

    So mit muss jetzt bloß noch die Zerlegung gemacht werden...

    Danke für die geänderten Zeilen, aber
    kannst du mir diesen Teil nochmal erklären?

    do
            {
                i = i + 1;
            }while (!primtest(i));
    
            while(y%i==0)
            {
                std::cout<<i<<" "<<y<<"\n";
                y = y/i;
            }
    

    Ich verwende allerdings irgentwie ungern ein do-while Schleife, geht das auch ohne?

    PS:Danke für das Lob!



  • Chillee schrieb:

    Ich verwende allerdings irgentwie ungern ein do-while Schleife, geht das auch ohne?

    Na, klar! Darf ich dazu goto verwenden?



  • Chillee schrieb:

    Ich verwende allerdings irgentwie ungern ein do-while Schleife, geht das auch ohne?

    Sauber? Eher weniger, wenn der Code mindestens einmal aufgerufen werden soll, und nicht unnötige Tempvariablen etc. verwendet werden...



  • Oh sorry, hab grad an was total anderes gedacht als das geschrieben habe. 😃
    Klar ein do-while schleife ist durchaus legitim ;)...bastel grad noch dran 😉 !



  • So denke habe die Lösung nun zusammen 🙂 !
    Wenn noch jemand Schwachstellen sieht, bitte bis spätestens Freitag posten...Danke!

    #include <iostream>
    
    // ------- Nebenfunktionen-------
    
    // >Eingabe
    int eingabe (void) {
      int x = 0;
      std::cout<<"Bitte geben sie eine natuerliche Zahl ein: ";
      std::cin>>x;
      while (x<1) {
        std::cout<<"\nDie eingegebene Zahl ist nicht natuerlich!\nBitte geben sie erneut eine natuerliche Zahl ein: ";
        std::cin>>x;
      }
      return x;
    }
    
    // >Test ob Primzahl
    bool primtest (int p) {
      int zaehler;
    
      if (p == 2) return 1;
    
      if (p %2 == 0) return 0;
    
      for (zaehler = 3; zaehler * zaehler <= p; zaehler = zaehler+2) {
        if (p % zaehler == 0) return 0;
      }
    
      return 1;
    }
    
    // >Primzahlzerlegung
    int primzer (int y) {
    
       int i = 2;
    
      while (y > 1) {
            while ((y%i != 0) || (primtest(i) == 0)) {
             i = i + 1;
        }
        std::cout<<i<<" ";
        y = y/i;
      }
      return 0;
    }
    
    // ------ Hauptfunktion -----------
    
    int main () {
      int n;
      int k;
    
      std::cout<<"Primfaktorzerlegung einer natuerlichen Zahl\n -------------------------\n "<<std::endl;
    
      n = eingabe();
      if (n == 1) std::cout<<"\nDie eingegebene Zahl laesst sich nur durch 1 teilen!"<<std::endl;
      else {
        k = primtest(n);
        if (k == 0) {
          std::cout<<"\nDie Zahl "<<n<<" laesst sich in folgende Primfaktoren zerlegen: "<<std::endl;
          primzer (n);
          std::cout<<std::endl;
        }
        else {
          std::cout<<"\n"<<n<<" ist eine Primzahl \nSie ist nur durch: "<<n<<" und 1 teilbar."<<std::endl;
        }
        }
    
      return 0;
    }
    


  • volkard schrieb:

    Doch, ich fürchte, die Bedingung ist völlig ohne Grund. Sowohl bei trial division als auch beim Sieb des Eratosthenes ist ein Vortest auf Primalität der Teiler Zeitverschwendung.

    OK, da hast Du recht. Hatte nicht bedacht, dass bei der hier gezeigten Methode der Rest durch die gefundenen Primfaktoren schnell kleiner wird und man dadurch nur einen Bruchteil des E. Siebes bräuchte. Eine Ausnahme allerdings: Die Eingabezahl ist selbst eine sehr große Primzahl, da ist das Sieb dann schneller (aber nur da 😉 ...).

    Man bräuchte so eine Art "dynamisches Sieb", das immer nur bis zur nächsten gefundenen Primzahl weitermacht (wobei, denke ich, der Verwaltungsaufwand das Projekt sprengen würde.).

    Übrigens habe ich hier
    http://www.hsg-kl.de/faecher/inf/algorithmus/standard/primfak/index.php
    einen ganz netten Algorithmus gefunden, der nach ersten Schätzungen bis etwa 600x schneller werden kann als der von Euch entwickelte - je nach Eingabezahl und vor allem bei sehr großen Primfaktoren (z.B. bei n = 532895). Bei vielen kleinen Faktoren schwindet dieser Vorsprung.

    Allerdings - er erfüllt die Bedingung der zwei getrennten Funktionen leider auch nicht. Und keine Ahnung, warum er funktioniert... Für Interessierte hier mal eine C-Version:

    void primfaktoren( int n )
    {
        while( n % 2 == 0 )
        {
        	cout << "2" << endl;
            n = n / 2;
        }
        while( n % 3 == 0 )
        {
        	cout << "3" << endl;
            n = n / 3;
        }
    
        int t = 5;
        int diff = 2;
    
        while( t*t <= n )
        {
            while( n % t == 0 )
            {
                cout << t << endl;
                n = n / t;
            }
    
            t = t + diff;
            diff = 6 - diff;
        }
    
        if( n > 1 )
        {
        	cout << n << endl;
        }
    }
    

    Viel Spaß noch weiterhin!



  • minastaros schrieb:

    Und keine Ahnung, warum er funktioniert...

    Wo haperts denn? Am t? t iteriert durch Primzahlkandidaten nach der simplen Analyse aus dem Link. Die Zeile mit der 6 ist ein Trick, um den Summanden zwischen 2 und 4 zu alternieren.



  • minastaros schrieb:

    Übrigens habe ich hier
    http://www.hsg-kl.de/faecher/inf/algorithmus/standard/primfak/index.php
    einen ganz netten Algorithmus gefunden, der nach ersten Schätzungen bis etwa 600x schneller werden kann als der von Euch entwickelte

    Allerdings nur 33% schneller als die Version vom 23 Nov 2010 22:33

    minastaros schrieb:

    Allerdings - er erfüllt die Bedingung der zwei getrennten Funktionen leider auch nicht.

    Das dürfte auch die entscheidende Bremse gewesen sein.
    Aber der Prof verlangt es eben.



  • Michael E. schrieb:

    Wo haperts denn? Am t?

    Nee, an der späten Zeit, war schon zu müde zum Denken... Lag grad schon im Bett, da ist es mir auch aufgegangen, was es mit der 6 auf sich hat.

    Allerdings glaube ich, dass bei großen Primfaktoren die immense Ersparnis durch das t*t in der while-Schleife kommt: Er bricht früh genug ab, während sich anderen Algorithmen bis zum Ende durchquälen, obwohl kein weiterer Faktor mehr gefunden werden kann.

    Gute Nacht also.



  • Chillee schrieb:

    Wenn noch jemand Schwachstellen sieht, bitte bis spätestens Freitag posten...Danke!

    Sieht gut aus! Die Ausgabe ist (verglichen mit meiner Version) höchstwahrscheinlich 😃 korrekt.
    Kleinste Mängel: 1 wird als Primzahl gewertet, du testest zwar, ob die Zahl 1 ist, in der entsprechenden Funktion würde es aber auch nicht fehl am Platze sein.
    Außerdem versuch mal 9876543210 als n einzulesen. Abhilfe schafft hier ein cin.clear() .
    Ansonsten top 👍.



  • minastaros schrieb:

    Allerdings glaube ich, dass bei großen Primfaktoren die immense Ersparnis durch das t*t in der while-Schleife kommt

    Ah, stimmt. Wir hatten zwar auch den Trick entdeckt und zaehler * zaehler <= p gemacht, aber nur in der Primzahl-Feststellung, nicht in der Primfaktoren-Zerlegung.



  • volkard schrieb:

    Ah, stimmt. Wir hatten zwar auch den Trick entdeckt und zaehler * zaehler <= p gemacht, aber nur in der Primzahl-Feststellung, nicht in der Primfaktoren-Zerlegung.

    Naja, probiert mal, das i * i bei Euch in die While-Schleife reinzupacken. Dann habt Ihr der Vorteil da auch.
    Macht doch mal ein paar Zeitmessungen (timeval-Struktur aus time.h) rein und lasst einmal primzer1( ) und einmal primzer2( ) laufen. Würde mich interessieren, wie die Unterschiede sind.
    Hab das mit Eurem, dem oben genannten Algorithmus und dem guten Eratosthenes gestern mal gemacht. Das Sieb hat dabei fürchterlich abgekackt... - es sei denn, man hat ihm eine große Primzahl gegeben... Nicht wirklich effizient... 😉

    Ein Tip noch: \n und endl gemischt sieht bei Printausgaben immer etwas unordentlich aus, weil sie ja (fast) das gleiche machen. Schreibt besser jede Zeile einzeln und immer ein endl dahinter. Sonst weiter so!



  • minastaros schrieb:

    Schreibt besser jede Zeile einzeln und immer ein endl dahinter. Sonst weiter so!

    Aber '\n' ist besser.



  • minastaros schrieb:

    Macht doch mal ein paar Zeitmessungen (timeval-Struktur aus time.h) rein und lasst einmal primzer1( ) und einmal primzer2( ) laufen. Würde mich interessieren, wie die Unterschiede sind.

    Ok. Aber bei den riesigen Laufzeiten kann ich auch einfach die von Code::Blocks angezeigte Gesamtlaufzeit nehmen.

    main:

    for(int i=1000000000;i<1000000000+10;++i){
    		std::cout<<i<<": ";
    		primzer(i);
    		std::cout<<'\n';
    	}
    

    Meßcode:

    int primzer (int y) {
    
    	int i = 2;
    
    	while (y > 1) {
    		while ((y%i != 0) || (primtest(i) == 0)) {
    			i = i + 1;
    		}
    		std::cout<<i<<" ";
    		y = y/i;
    	}
    	return 0;
    }
    

    Ausgabe:

    1000000000: 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5
    1000000001: 7 11 13 19 52579
    1000000002: 2 3 43 983 3943
    1000000003: 23 307 141623
    1000000004: 2 2 41 41 148721
    1000000005: 3 5 66666667
    1000000006: 2 500000003
    1000000007: 1000000007
    1000000008: 2 2 2 3 3 7 109 109 167
    1000000009: 1000000009
    
    Process returned 0 (0x0)   execution time : 73.796 s
    

    Soweit, so langsam.

    Jetzt die i*i-Beschleunigung (uih, häßlich reingequetscht):

    int primzer (int y) {
    
    	int i = 2;
    
    	while (y > i) {
    		while ((y%i != 0) || (primtest(i) == 0)) {
    			if(i*i>y){
    				std::cout<<y<<" ";
    				return 0;
    			}
    			i = i + 1;
    		}
    		std::cout<<i<<" ";
    		y = y/i;
    	}
    	return 0;
    }
    
    Process returned 0 (0x0)   execution time : 0.015s
    

    Um weiter einen Unterschied sehen zu können, ziehe ich die main-Schleife größer.

    41.046 s
    

    Jetzt mit i*i-Beschleunigung und ohne primetest:

    36 s
    


  • Nochmals vielen Dank für die zahlreichen Antworten.

    Leider komm ich zwischendrinne manchmal nicht mehr mit, da mir wahrscheinlich der Hintergrund fehlt. Ich habe bloß verstanden das mein Programm bei großen Zahlen zu langsam ist oder? Wie mach ich das besser? Wäre cool wenn mir das jemand auch erklären könnte, da ich sonst wieder bloß Bahnhof verstehe 😃 !

    @ Vicious Falcon: Danke! Aber was meinst du mit: "die 1 wird als Primzahl gewertet" . Ich nehm den Fall der 1 doch in der main vorher raus durch eine IF-Schleife. Ja und das mit "9876543210" hab ich schon festgestellt, da kommt er wie in eine Endlosschleife. Aber Warum? Und wie, wo und warum kann ich das mit einem cin.clear() beheben?



  • Ich hatte ja geschrieben, dass es nur eine Kleinigkeit ist, in einer allgemein gültigen Funktion sollte aber auch der Fall n==1 betrachtet werden.

    if (p==1 || p%2 == 0) return false;
    

    Bei dem Einlesen kannst du überprüfen, ob alles geklappt hat

    #include <limits>
    int eingabe () {
    	int x = 0;
    	std::cout<<"Bitte geben sie eine natuerliche Zahl ein: ";
    	while (!(std::cin>>x) || x<1) // irgendwas ging schief
    	{
    		std::cout<<"\nDie eingegebene Zahl ist nicht natuerlich!\nBitte geben sie erneut eine natuerliche Zahl ein: ";
    		if(cin.fail()) // Input konnte nicht konvertiert werden
    		{
    			std::cin.clear(); // Failbit löschen
    			std::cin.ignore(std::numeric_limits<streamsize>::max(),'\n'); // den Rest der Zeile ignorieren und nochmal probieren
    		}
    	}
    	return x;
    }
    

    Eine Eingabe von 4561gfrg ist immer noch gültig, es wird bis zum Auffinden von 'g' konvertiert und somit 4561 zurück gegeben.



  • Okay danke, aber die Zeile

    std::cin.ignore(std::numeric_limits<streamsize>::max(),'\n');
    

    verstehe ich noch nicht bzw. was sagt diese aus? löscht sie einfach nur die Buchstaben von der Beispieleingabe?

    Und dann zu

    while (!(std::cin>>x) || x<1)
    

    Diese Schreibweise kenne ich noch nicht, aber ich interpretiere mal so:
    Auf Grund des Ausrufezeichens wird noch einer Eingabe gefragt und diese wird auch kleiner 1 getestet oder?
    Aber wenn ich nun das Beispiel eingebe "4561gfrg" was für einen Wert hat dies dann? Ich mein würde er dann auch in die Schleife gehen?
    Weil meines Anfängerwissen haben Buchstaben letzten Endes auch bloß Zahlwerte und diese wären ja dann größer 1 oder?

    Sorry für die vielen Fragen aber lerne es erst seit 1,5 Monaten.



  • Ich bin mir nicht sicher, ob ihr das überhaupt abfragen müsst, oder einfach von gültigen Eingaben ausgehen könnt.
    Trotzdem eine kurze Erklärung. Wenn cin eine Eingabe nicht konvertieren kann, wird das "Failbit" gesetzt. Die Eingabe verbleibt dabei aber im stream. Jede weitere Eingabe wird ignoriert, bis dieses "Failbit" gelöscht wurde.
    Das heißt, die Vorgehensweise ist Folgende:

    • Zahl einlesen.
    • Überprüfen, ob der Eingabestream gültig ist.
    • Wenn nicht, mit cin.clear() das "Failbit" löschen, mit cin.ignore(..) die Eingabe verwerfen und es erneut probieren.

    Der Aufruf

    std::cin.ignore(std::numeric_limits<streamsize>::max(),'\n');
    

    löscht alles, bis der delim , in diesem Fall '\n', gefunden wurde.

    std::numeric_limits<streamsize>::max()
    

    liefert den größtmöglichen Wert für den typedef streamsize.
    Die Bedingung

    while (!(std::cin>>x) || x<1)
    

    bedeutet nichts weiter, als dass abgefragt werden soll, ob der Stream (cin) in einem fehlerhaften Zustand, ODER ob x<1 ist. Nur wenn eine dieser beiden Bedingungen erfüllt ist, wird der Schleifenkörper betreten, ansonsten ist alles glatt gegangen und die Funktion gibt den eingelesenen Wert zurück.



  • Okay das macht Sinn dankeschön!

    Aber muss dann vor deiner ersten While-Schleife nicht noch ein

    std::cin>>x;
    

    stehen?


Anmelden zum Antworten