3. [Gelöst] Primzahlenprogramm

[Gelöst] Primzahlenprogramm

  • S

    icarus2 schrieb:

    std::vector wird erzeugt bevor main() ausgefuehrt wird (warum?).

    Weil ich ihn auch für

    findeZahl(int welche);

    brauche.

    0
  • Mod

    SuperManitu schrieb:

    icarus2 schrieb:

    std::vector wird erzeugt bevor main() ausgefuehrt wird (warum?).

    Weil ich ihn auch für

    findeZahl(int welche);

    brauche.

    Dann übergib ihn doch.

    0
  • R

    Zu aller erst: In Zeile 20 muss es "int main() {" heißen. Mein Compiler akzeptiert void gar nicht erst^^

    In Zeile 37 könntest du die Größe von zahlen setzen:
    zahlen = vector<int>(maxi);

    Und in Zeile 8 würde ich schreiben:
    vector<int> zahlen;

    Es könnte ja sein, dass in dem uninitialisierten maxi 2 Milliarden drin steht...

    Dein Programm terminiert bei mir trotzdem nicht, aber da weiß ich momentan auch nicht den Fehler.

    0
  • N

    Warum machst du es dir so verdammt kompliziert? Warum machst du es nicht einfach so?

    int main ()
{
    std::cout<<"Bitte Bereich eingeben."<<std::endl;
    int low,high;
    std::cin>>low>>high;

    if(low>high)
    std::swap(low,high); 

    std::cout<<std::endl<<"Die Primzahlen in diesem Bereich sind:"<<std::endl;
    for(int i=low;i<=high;++i)
    {
        if(isprime(i))  //Funktion, die einfach nur guckt, ob die Zahl eine Primzahl ist.
           std::cout<<i<<std::endl;
    }
}
    0
  • W

    Hallo SuperManitu,

    Das Programm enthält einen ganzen Sack von Fehlern. Ein wesentlicher Punkt sind globale Variablen, die zwar nicht direkt, aber in Deinem Fall indirekt zu Fehlern führen. Weiter musst Du sehr sauber zwischen dem Index auf den vector 'zahlen' und dem Wert einer Zahl trennen. Das tust Du in mindestens drei Fällen nicht. Und wenn Du eine Zahl suchst (Funktion 'finde'), so musst Du immer berücksichtigen, dass Du die gesuchte Zahl nicht findest. Das hast Du auch in keinem Fall getan.
    Anbei die (oberflächlich) korrigierte Fassung:

    #include <iostream>
#include <vector>

int findeZahl( const std::vector<int>& zahlen, int welche){
    int ort = -1;
    for (int s=0; s<zahlen.size(); ++s){
        if(zahlen[s]==welche){
            ort=s;
            break;
        }
    }
    return ort;
}

int main() {
    using namespace std;

    // --   Eingabe
    int mini, maxi, gefunden;
    cout<<"Geben sie das Minimum ein: ";
    cin>>mini;

    cout<<"Geben sie das Maximum ein: ";
    cin>>maxi;

    if(mini>maxi){
        int tmp=mini;
        mini=maxi;
        maxi=tmp;
    }
    vector<int> zahlen(maxi);

    // --   Vorbelegung 2,3,4,5,... Achtung index := Zahl-2
    for (int i = 0; i<(maxi-2);i++){
        zahlen[i] = i+2;
    }

    // --   Sieben
    for(int z=0;z<zahlen.size();z++){
        int aktuell = -1;
        for(int r=z;r<zahlen.size();r++){
            if(zahlen[r] != 0){
                aktuell=zahlen[r]; // r ist index; 'aktuell' ist Zahl!
                break;
            }
        }
        if( aktuell > 0 )
        {
            for(int e = aktuell*2;e<maxi;e+=aktuell){
                gefunden = findeZahl(zahlen, e);
                if( gefunden >= 0 ) // berücksichtige, wenn die Zahl nicht gefunden wird
                    zahlen[gefunden]=0;
            }
        }
    }
    // --   alles, was nicht Primzahl ist, beseitigen
    int anzahlGeloescht=0;
    for( int idx_zu_loeschen; (idx_zu_loeschen = findeZahl(zahlen, 0)) >= 0; ++anzahlGeloescht ) {
        zahlen.erase( zahlen.begin() + idx_zu_loeschen );
    }

    cout<<endl<<"Primzahlen sind:"<<endl;
    for(int k=0;k<zahlen.size();k++){ // mini ist Zahl; k ist Index, und der Index ist durch das Löschen oben ungültig!
        if( zahlen[k] >= mini ) cout<<zahlen[k]<<endl;
    }

    cin.get();
}

    Bleibt noch der Fehler der zu hohen Komplexität (Das Verhalten der Laufzeit bei großen Datenmengen). Was das bedeutet, merkst Du dann, wenn Du das von mir korrigierte Programm, mal mit einem Max-Wert von z.B. 100000 laufen lässt. 😉

    Nymer schrieb:

    Warum machst du es dir so verdammt kompliziert?

    wohl, weil SuperManitu das Sieb des Eratosthenes programmieren wollte.

    Gruß
    Werner

    0
  • W

    .. und weil es draußen regnet, noch mal eine um den Komplexitätsfehler korrigierte Fassung.
    Da kannst Du jetzt auch 10Millionenn als Obergrenze eingeben, das Programm beginnt schon nach 1-2sec mit der Ausgabe.

    #include <algorithm> // remove_copy_if
#include <cmath> // sqrt
#include <iostream>
#include <iterator> // ostream_iterator
#include <vector>

int main() {
    using namespace std;

    // --   Eingabe
    int mini, maxi;
    cout<<"Geben sie das Minimum ein: ";
    cin>>mini;

    cout<<"Geben sie das Maximum ein: ";
    cin>>maxi;

    if(mini>maxi){
        int tmp=mini;
        mini=maxi;
        maxi=tmp;
    }
    vector<int> zahlen(maxi-1);

    // --   Vorbelegung 2,3,4,5,... Achtung index := Zahl-2
    for( size_t i = 0; i<zahlen.size(); ++i) {
        zahlen[i] = int(i+2);
    }

    // --   Sieben
    const size_t maxIdx = size_t(sqrt( double(maxi) ))-1; // bis Wurzel(maxi) reicht auch
    for( size_t idx=0; idx < maxIdx; ++idx )
    {
        const int primzahl = zahlen[idx];
        if( primzahl == 0 )
            continue; // war doch keine

        for( std::size_t idx_no_prime = idx+primzahl; idx_no_prime < zahlen.size(); idx_no_prime += primzahl )
            zahlen[ idx_no_prime ] = 0; // alle Vielfache von Primzahlen sind keine
    }

    // --   alles, was nicht Primzahl ist, beseitigen und den Rest ausgeben
    remove_copy_if( zahlen.begin(), zahlen.end(), ostream_iterator< int >( cout, "\n" )
        , [mini]( int zahl ) { return zahl == 0 || zahl < mini; } );

    cin.get();
}

    Gruß
    Werner

    0
  • S

    Danke für die vielen Antworten!!

    Werner Salomon schrieb:

    Nymer schrieb:

    Warum machst du es dir so verdammt kompliziert?

    wohl, weil SuperManitu das Sieb des Eratosthenes programmieren wollte.
    Werner

    Stimmt.

    Ich hatte schon ein anderes, das einfach alle Zahlen außprobiert hat, und die die sich nur zwei mal Teilen lassen außgeben lassen.
    War aber sehr rechenaufwendig.

    0
  • S

    Danke.

    Ich stelle dieses Thema auf gelöst.

    0
  • R

    Das Thema Primzahlen ist immer mal wieder Thema hier.
    Da Du Anfänger zu sein scheinst, schau Dir doch mal folgenden alten Thread an:

    http://www.c-plusplus.net/forum/286485

    Für eine schnelle Primzahlenberechnung nach dem Sieb des E. solltest Du Dir auch überlegen, einen vector<bool> zu benutzen.

    0
  • ?

    redrew99 schrieb:

    einen Vector<bool> zu benutzen.

    vector<bool> ist doch verbuggt, oder wie war das noch?

    0
  • Mod

    out schrieb:

    redrew99 schrieb:

    einen Vector<bool> zu benutzen.

    vector<bool> ist doch verbuggt, oder wie war das noch?

    Nein, keine Bugs. Er ist bloß kein regulärer STL-Container. Man darf ihn aber gerne benutzen. Bloß nicht an den Stellen, wo die speziellen Eigenschaften benutzt werden, die er nicht erfüllt (z.B. bool& foo = boolvector[0]; wird böse schiefgehen).

    0

  • out schrieb:

    redrew99 schrieb:

    einen Vector<bool> zu benutzen.

    vector<bool> ist doch verbuggt, oder wie war das noch?

    Nö, nicht verbuggt, sondern eine Spezialisierung, die sich nicht immer so verhält, wie man es erwarten würde. Grund dafür ist, dass intern genau ein Bit für jeden bool benutzt wird (wenn der vector<bool> ein Byte allokiert bringt er darin 8 Bit unter). Das führt bei Sachen wie vector<bool>::size() * sizeof( bool ) zu falschen Werten.

    0
Anmelden zum Antworten