problem mit array bei primzahlensuche
-
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.
-
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.
-
Das ist mir klar. Kam das so rüber?
-
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)
-
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.
-
...
-
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.
-
Darum auch "i.A.".
-
nopemrmod schrieb:
Darum auch "i.A.".
Wenn du mit 10% die Allgemeinheit meinst
-
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 }
-
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.
-
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'; }
-
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.
-
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.
-
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
-
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.
-
Sone schrieb:
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.
Ich lach mich tot.
vector<bool>ist fast so gut wie
map<int,bool>oder Dein
vector<pair<int, bool>>Schau:
#include <vector> #include <iostream> #define first UNUSED 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);//Dieses +2 ist dran schuld! for( unsigned ct = 0; ct < vec.size(); ++ct ) if( vec[ct].second ) { // int value = vec[ct].first; int value = ct+2; for( unsigned multiple = value*value; multiple < vec.size() + 2; multiple += value ) vec[multiple - 2].second = false; } /// Ausgabe: for( unsigned ct = 0; ct < vec.size(); ++ct ) if( vec[ct].second ) // cout << vec[ct].first << ", "; cout << ct+2 << ", "; }
-
...
-
ok super, da habe ich noch einiges auszuprobieren und nachzulesen... hab mal überlegt, meine methode sollte O(N^2/ln(N)) sein, das Sieb von E ist ja O(N), hab bei Wikipedia noch das Sieb von Aktin gefunden,das anscheinend O(N/(ln(ln(N))) ist, was ja auch nicht viel besser als O(N) ist^^ gibt es noch einen besseren algorithmus zur primzahlenbestimmung der schneller ist?
-
neuhier123d schrieb:
ok super, da habe ich noch einiges auszuprobieren und nachzulesen... hab mal überlegt, meine methode sollte O(N^2/ln(N)) sein, das Sieb von E ist ja O(N), hab bei Wikipedia noch das Sieb von Aktin gefunden,das anscheinend O(N/(ln(ln(N))) ist, was ja auch nicht viel besser als O(N) ist^^ gibt es noch einen besseren algorithmus zur primzahlenbestimmung der schneller ist?
Eigentlich macht das Sieb des E alle anderen Platt.
http://code.google.com/p/primesieve/
Es ist auch recht leicht, es pfiffig zu implementieren.Mir ist unbekannt, ab wo das Sieb des Atkin schneller wird, aber wohl schon erst bei recht großen Zahlen. Ups, kriegt man es auch so einfach cache-friendly?
