3. problem mit array bei primzahlensuche

problem mit array bei primzahlensuche

  • ?

    Hallo zusammen, habe gerade angefangen mir c++ beizubringen und als eines der ersten programme mal diese primzahlensuche (sieb des ereratosthenes) geschrieben:

    #include <iostream>

int main () {

    int arr[1400];
    arr[0]=2;
    arr[1]=3;
    int v;
    int i=3;
    int prim =1;

    while(i<10000){
    i++;
    v=0;              
                  while(v<=prim){
                               if (i%arr[v]==0){break; }
                               if(v==prim){
                                           prim++;
                                           arr[prim]=i;
                                           }
                               v++;
                                 }

                 }
    int zz=0;
    while(zz<=prim){
                    std::cout<<arr[zz]<<"  ";
                    zz++;
                    }
    std::cout<<" Primzahlen gefunden:"<<prim ;
    getchar();
    return 0;

}

    das funktioniert soweit auch, nur wenn ich größere primzahlen suchen will (zb bis 20000) dann muss ich das array größer machen und es kommt immer zu einem crash des programms...woran liegt das?

    0
  • N

    Nicht genug Speicher.
    Allokiere das Array dynamisch (std::vector), dann ist es auf dem Heap, dort ist in der Regel mehr Platz (beim Computer).

    0
  • K

    Das ist gar nicht das Sieb des Eratosthenes. Da hast du wohl etwas Missverstanden.

    Nimm std::vector statt Arrays. Das macht das ganze viel einfacher.

    Um den Code lesbarer zu kriegen, kannst du den Primzahltest auch in einer Funktion auslagern. Z.B. so:

    #include <iostream>
#include <vector>

bool gemeinsamer_teiler(std::vector<long> const& pri, long kan)
{
    ...
}

int main()
{
    std::vector<long> primzahlen = {2,3};
    for (long kandidat=5; kandidat<=20000; ++kandidat) {
        if (!gemeinsamer_teiler(primzahlen,kandidat)) {
            primzahlen.push_back(kandidat);
        }
    }
    for (long p : primzahlen) {
        std::cout << p << '\n';
    }
}

    Das const& da macht aus pri eine Referenz, die sich wegen des Aufrufs in main auf primzahlen bezieht, wobei aber nur Lesezugriff gewährt wird. Dadurch verhindert man eine unnötige Kopie, was bei Vektoren ganz praktisch ist, weil das Kopieren von diesen Dingern potentiell teuer ist.

    Ich hoffe, Du hast dir ein schlaues Buch besorgt. Woher hast du die Verwendung von rohen Arrays ( int[] )?

    Viel Erfolg!

    0
  • ?

    ok super, vielen dank für die vorschläge, das mit einem starren array zu machen ist wohl nicht wirklich der eleganteste weg...habe diese array verwendung nicht aus einem buch, konnte mich aber erinnern so ein programm vor vielen jahren mal in basic geschrieben zu haben und ich habe es dann einfach in c++ "übersetzt". trotzdem verstehe ich noch nicht ganz das problem mit dem array, in zeiten von ram im gb bereich müsste ich doch ein array mit ein paar 1000 ints resevieren können

    0
  • N

    Jein.
    Es gibt verschiedene Arten von Speicher (unter den meisten Computersystemen, ist aber nicht im Standard festgelegt).
    Dadrunter ist der Stack und der Heap. Im Stack landen alle Variablen, die du normal in Funktionen deklarierst. Im Heap ist der Speicher, der via new angefordert wurde. In der Regel ist der Heap wesentlich größer als der Stack. In den Stack deines Rechners passt offenbar nicht dieses Array. Wenn du es aber dynamisch allokierst (mit new[], empfehle aber std::vector, der macht das automatisch und löscht das auch für dich), klappt es.

    0
  • Mod

    Nathan, der Stack ist kein physisches Ding im Rechner. Der Compiler erzeugt bloß Code, der sich ein Stückchen des Gesamtspeichers für die automatischen Variablen reserviert und den Rest als dynamischen Speicher frei lässt. Die Stackgröße ist daher bloß eine Zahl in deiner Executable.

    0
  • N

    Das ist mir klar. Kam das so rüber?

    0
  • ?

    ok d.h. ich könnte theoretisch die compilereinstellungen ändern um mehr platz für das array zu bekommen? (schon klar das sollte ich nicht machen, nur zum verständnis)

    0
  • ?

    SeppJ schrieb:

    Der Compiler erzeugt bloß Code, der sich ein Stückchen des Gesamtspeichers für die automatischen Variablen reserviert und den Rest als dynamischen Speicher frei lässt. Die Stackgröße ist daher bloß eine Zahl in deiner Executable.

    Nein, das Stacklimit ist i.A. Sache des Betriebssystems.

    0

  • ...

    0
  • Mod

    neuhier123d schrieb:

    ok d.h. ich könnte theoretisch die compilereinstellungen ändern um mehr platz für das array zu bekommen? (schon klar das sollte ich nicht machen, nur zum verständnis)

    Jain. Siehe unten.

    nopemrmod schrieb:

    SeppJ schrieb:

    Der Compiler erzeugt bloß Code, der sich ein Stückchen des Gesamtspeichers für die automatischen Variablen reserviert und den Rest als dynamischen Speicher frei lässt. Die Stackgröße ist daher bloß eine Zahl in deiner Executable.

    Nein, das Stacklimit ist i.A. Sache des Betriebssystems.

    Jain. Kommt auf das System an. Es gibt da so ein recht verbreitetes System, bei dem das Sache der Executable ist.

    0
  • ?

    Darum auch "i.A.".

    0
  • Mod

    nopemrmod schrieb:

    Darum auch "i.A.".

    Wenn du mit 10% die Allgemeinheit meinst 🙄

    0
  • S

    Hmm.

    Was auch schön wäre, wäre eine Kombination mit std::remove_if:

    #include <vector>
#include <iostream>
#include <numeric>
#include <iterator>
#include <algorithm>

int main()
{
    using namespace std;

    vector<int> vec(1000); // Platz für Tausend Zahlen

    iota( begin(vec), end(vec), 1 ); // vec mit Zahlen von 1 bis 1000 füllen

    for( unsigned ct = 2; ct < vec.size(); ++ct ) // Alle Teiler in einer Schleife durchgehen.
        vec.erase( remove_if( begin(vec), end(vec), [=](int i){ return i % ct == 0; } ), end(vec) ); /// Alle Elemente aus vector entfernen die sich durch ct teilen lassen.

    copy( begin(vec), end(vec), ostream_iterator<int>(cout, ", ") ); // vec ausgeben (Zahlen durch Komma getrennt
}
    0
  • V

    Sone schrieb:

    Hmm.

    Was auch schön wäre, wäre eine Kombination mit std::remove_if:

    #include <vector>
#include <iostream>
#include <numeric>
#include <iterator>
#include <algorithm>

int main()
{
    using namespace std;

    vector<int> vec(1000); // Platz für Tausend Zahlen

    iota( begin(vec), end(vec), 1 ); // vec mit Zahlen von 1 bis 1000 füllen

    for( unsigned ct = 2; ct < vec.size(); ++ct ) // Alle Teiler in einer Schleife durchgehen.
        vec.erase( remove_if( begin(vec), end(vec), [=](int i){ return i % ct == 0; } ), end(vec) ); /// Alle Elemente aus vector entfernen die sich durch ct teilen lassen.

    copy( begin(vec), end(vec), ostream_iterator<int>(cout, ", ") ); // vec ausgeben (Zahlen durch Komma getrennt
}

    Du hast hiermit die einzigen beiden unter 1000 liegenden Primzahlen 420 und 840 entdeckt. 😡

    0
  • V

    neuhier123d schrieb:

    Hallo zusammen, habe gerade angefangen mir c++ beizubringen und als eines der ersten programme mal diese primzahlensuche (sieb des ereratosthenes) geschrieben

    Nein, Du hast das Sieb des E nicht implementiert, sondern Trial Division mit sich gemerkten Primzahlen.
    Ungefähr sowas:

    #include <iostream>
#include <vector>
using namespace std;

bool istTeilerDrin(vector<int>& teiler,int zahl){
    for(auto t:teiler){
                                     //<-
        if(zahl%t==0)
            return true;
    }
    return false;
}

int main ()
{
    vector<int> primzahlen{2};

    for(int kandidat=3;kandidat<10000;kandidat+=2)
        if(!istTeilerDrin(primzahlen,kandidat))
            primzahlen.push_back(kandidat);

    for(auto p:primzahlen)
        cout<<p<<' ';

    cout<<" Primzahlen gefunden:"<<primzahlen.size()<<'\n';
}
    0
  • S

    volkard schrieb:

    Du hast hiermit die einzigen beiden unter 1000 liegenden Primzahlen 420 und 840 entdeckt. 😡

    Ach, mein Verfahren ist bullshit. 👎

    Bzw. eigentlich auch nicht, s.u. - da war ein Denkfehler.

    0
  • S

    Hier das Sieb des Eratosthenes:

    #include <vector>
#include <iostream>

int main()
{
    using namespace std;

    unsigned const N = 1000;

    vector<pair<int, bool> > vec(N - 1); // Platz. Erster Wert ist die Zahl, der zweite bool-Wert gibt an ob diese Zahl noch eine Primzahl sein könnte.

    for( unsigned ct = 0; ct < vec.size(); ++ct )
        vec[ct] = make_pair(ct + 2, true);

    for( unsigned ct = 0; ct < vec.size(); ++ct )
        if( vec[ct].second )
        {
            int value = vec[ct].first;

            for( unsigned multiple = value*value; multiple < vec.size() + 2; multiple += value ) /// Durch alle Vielfachen gehen und diese als Nicht-Prim markieren
                vec[multiple - 2].second = false;
        }

    /// Ausgabe:
    for( unsigned ct = 0; ct < vec.size(); ++ct )
        if( vec[ct].second )
            cout << vec[ct].first << ", ";
}

    Ideone: http://ideone.com/JnCKGc

    Ist jetzt ganz sicher richtig.

    0
  • S

    Meine vorherige Version ist an sich auch möglich, muss aber angepasst werden:

    #include <vector>
#include <iostream>
#include <numeric>
#include <iterator>
#include <algorithm>

int main()
{
    using namespace std;

    vector<int> vec(1000); // Platz für Tausend Zahlen

    iota( begin(vec), end(vec), 2 ); // vec mit Zahlen von 2 bis 1001 füllen

    for( unsigned ct = 2; ct < vec.size() - 2; ++ct ) // Alle Teiler in einer Schleife durchgehen.
        vec.erase( remove_if( begin(vec) + ct + 1, end(vec), [=](int i){ return i % ct == 0; } ), end(vec) ); /// Alle Elemente aus vector entfernen die sich durch ct teilen lassen. 
/// Im Gegenteil zu der ersten, nicht funktionierenden Methode wird hier nicht bei begin(vec) sondern bei begin(vec) + ct + 1 angefangen, wodurch der Fehler dass der Modul selbst entfernt wird, nicht  mehr auftritt.

    copy( begin(vec), end(vec), ostream_iterator<int>(cout, ", ") ); // vec ausgeben (Zahlen durch Komma getrennt
}

    Ideone: http://ideone.com/wisLEG

    0
  • V

    Sone schrieb:

    Meine vorherige Version ist an sich auch möglich, muss aber angepasst werden:

    #include <vector>
#include <iostream>
#include <numeric>
#include <iterator>
#include <algorithm>

int main()
{
    using namespace std;

    vector<int> vec(1000); // Platz für Tausend Zahlen

    iota( begin(vec), end(vec), 2 ); // vec mit Zahlen von 2 bis 1001 füllen

    for( unsigned ct = 2; ct < vec.size() - 2; ++ct ) // Alle Teiler in einer Schleife durchgehen.
        vec.erase( remove_if( begin(vec) + ct + 1, end(vec), [=](int i){ return i % ct == 0; } ), end(vec) ); /// Alle Elemente aus vector entfernen die sich durch ct teilen lassen. 
/// Im Gegenteil zu der ersten, nicht funktionierenden Methode wird hier nicht bei begin(vec) sondern bei begin(vec) + ct + 1 angefangen, wodurch der Fehler dass der Modul selbst entfernt wird, nicht  mehr auftritt.

    copy( begin(vec), end(vec), ostream_iterator<int>(cout, ", ") ); // vec ausgeben (Zahlen durch Komma getrennt
}

    Ideone: http://ideone.com/wisLEG

    Trotzdem bist Du wieder auf der Insel des Bullshits.

    Ich hab mein Verfahren gerade mal geändert, daß es nicht alle Primzahlen bis Obergrenze und dann die Anzahl, sondern nur die Anzahl ausgibt.

    Für Obergrenze 1000000 braucht es 12.4s.
    Mhhm. Das müßte man beschleunigen.

    Oh, muss nur

    if(t*t>zahl)
            break;

    reinschreiben und bin bei 0.05s. Bei Dir sehe ich gar nicht, wo ich es reinschreiben sollte.

    0
Anmelden zum Antworten