Anfängerproblemchen mit recht schwieriger Aufgabe



  • Hallo liebe C++ - Gemeinde,

    ich habe folgende Aufgabe:

    Schreiben Sie ein Programm für die Primfaktorzerlegung einer natürlichen Zahl. Eine Funktion für die Eingabe soll prüfen, ob diese überhaupt zulässig ist (natürliche Zahl) und sonst zur erneuten Eingabe auffordern. Die Generierung/Prüfung von Primzahlen sowie die eigentliche Zerlegung sind in eigenständigen Funktionen zu realisieren.

    Ich habe dazu nun folgenden Code geschrieben:

    #include <iostream>
    
    // ------- Nebenfunktionen-------
    
    // >Eingabe
    int eingabe (int x) {
      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;
    }
    
    // >Test ob Primzahl
    int primtest (int p) {
      int zaehler;
    
      if (p < 2) return 0;
    
      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
    void primzer (int y) {
    
       int i;
    
      while (y > 1) {
        i = 2;
    
        while ((y%i != 0) && (primtest(i) == 0)) {
          i = i + 1;
        }
        std::cout<<i<<" "<<y<<"\n";
        y = y/i;
      }
    }
    
    // ------ Hauptfunktion -----------
    
    int main () {
      int n;
    
      std::cout<<"Primfaktorzerlegung einer natuerlichen Zahl\n ------------------------- "<<std::endl;
    
      eingabe (n);
    
      primzer (n);
    
      return 0;
    }
    

    Mein Problem ist nun: Ich denke eigentlich müssten die einzelnen Funktionen(Eingabe, Primzahlentest, Primzahlenzerlegung) von der Sache her stimmen, lass mich natürlich auch eines besseren Belehren! Doch wenn ich dieses Programm nun teste, wird der eingegebene Wert von der Eingabefunktion nicht weiter an die zweite Funktion übergeben (so sieht das zumindest aus wenn ich "y" mit ausgeben lasse) und ich komm einfach nicht drauf warum?! Ich hab da jetzt schon eine Ewigkeit dran rumprobiert...doch leider ohne Erfolg!

    Kann mir hier evtl. jemand weiter helfen?

    Vielen Dank schonmal,
    Beste GRüße,
    Chillee



  • du hast zwei Möglichkeiten:
    a. Wert per Referenc übergeben
    b. Den Rückgabewert einer Variablen zuweisen

    a. sieht so aus:

    int eingabe (int& x)
    

    b. sieht so aus:

    n = eingabe (n);
    


  • Chillee schrieb:

    Doch wenn ich dieses Programm nun teste, wird der eingegebene Wert von der Eingabefunktion nicht weiter an die zweite Funktion übergeben

    Änder das mal in:

    int eingabe () {
    int x;
    ...
    

    und:

    ...
    n = eingabe();
    


  • Gratulation! Du hast Den Draht zum Rechner. Selten so einen schönen Newbie-Code gesehen. Weiter so!
    Ich hab ihn mal fertiggemacht. (Durch Wegwerfen der primetest-Bedingung, wie Du überrascherweise festestellen wirst, hihi. 🙂 )

    #include <iostream>
    
    // ------- Nebenfunktionen-------
    
    // >Eingabe
    int eingabe ()
    {
        int x;
        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;
    }
    
    // >Test ob Primzahl
    int primtest (int p)
    {
        int zaehler;
    
        if (p < 2) return 0;
    
        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
    void primzer (int y)
    {
    
        int i;
    
        while (y > 1)
        {
            i = 2;
    
            while ((y%i != 0) )
            {
                i = i + 1;
            }
            std::cout<<i<<" "<<y<<"\n";
            y = y/i;
        }
    }
    
    // ------ Hauptfunktion -----------
    
    int main ()
    {
    
        std::cout<<"Primfaktorzerlegung einer natuerlichen Zahl\n ------------------------- "<<std::endl;
    
        int n=eingabe();
    
        primzer(n);
    
        return 0;
    }
    


  • Das mag zwar funktionieren, war aber nicht die Aufgabe: Berechnung der Primzahlen und die Zerlegung sollen in zwei getrennten Funktionen erfolgen. Und das nicht ohne Grund. Dein Algorithmus ist zudem recht ineffektiv:

    • Nach jeder Teilung y=y/i wird i wieder auf 2 gesetzt, auch wenn alle Primfaktoren 2 bereits längst erledigt sind. Von da an werden alle Zahlen jedes Mal aufs Neue durchprobiert, um zum nächsten Primfaktor des aktuellen y zu gelangen, anstatt beim aktuellen i einfach weiterzumachen.
    • 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.

    Tip: Der Herr Eratosthenes hat da mal so ein Sieb erfunden...



  • 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
    

Log in to reply