Primzahlen ausgeben

unskilled

Joar - danke ^^
das hatte sich ja aber angeblich geklärt... er meinte ja, er hats jz (wahrscheinlich hat er es einfach sein lassen, aber das is ne mein prob )

zum thread an sich:
es wäre eben au darum gegangen, sich zumindest mit dem thema primzahlen zu beschäftigen... er wusste weder was das ist, noch wie das geht...

egal - closed nehm ich einfach ma an ^^
tom

ps: shift is doof ^^

//edit:
@john:
1. Du hast die 3 zweimal in dem Array drin...
2. Is eigtl komplett mein Algorithmus - nur ineffektiver : P

*john 0

unskilled schrieb:

//edit:
@john:
1. Du hast die 3 zweimal in dem Array drin...
2. Is eigtl komplett mein Algorithmus - nur ineffektiver : P

<Edit> Geschriebene (bei mir ausgeführte) und gepostete Version unterschieden sich voneiander.
Nein, die 3 kommt nur einmal drin vor, liegt an den Testbedingungen.
</Edit>
Als ich das eingegeben habe, hattest Du noch nicht gepostet.
Nein, dein Algorithmus nimmt alle ungerade Zahlen als Testzahlen, das ist deutlich langsamer, wenn man hinreichend große Zahlen hat.

P.S. Wenn es richtig große Zahlen sein sollen, sollte man sich das hier durchlesen http://de.wikipedia.org/wiki/Zahlkörpersieb

unskilled

loooooooooooool...

1. "die 3 kommt nur einmal drin vor"

primes.push_back(3); 

for (long long i = 3; i != max; i+=2) // i == 3
 { 
                long long test (1); 
                bool p (true); 

                while (p && ((primes[test]*primes[test]) <= i))
                { //p == true; primes[1] == 3 ==> primes² == 9 => false => abbruch
                        if (0 == (i % primes[test++])) { 
                                p = false; 
                                break; 
                        } 
                } 
                if (true == p) // p == TRUE!!!!
                        primes.push_back(i); //PUSH_BACK (3)
        }

2. "Als ich das eingegeben habe, hattest Du noch nicht gepostet."
Hast du 6 Stunden gebraucht? xD
14.30 und 15.07Uhr ich) / 21.40Uhr (du) oder so waren die Zeiten : P

3. "Nein, dein Algorithmus nimmt alle ungerade Zahlen als Testzahlen, das ist deutlich langsamer, wenn man hinreichend große Zahlen hat."
Glaub ich nicht dran.... (siehe das Posting 14.30Uhr)
Du nimmst vector - vector hat meines erachtens aber eine max.größe und ist langsamer, weil er ständig neuen Speicher alloziiert - mein Array hingegen ist statisch, wird immer, wenn es voll ist in ne Datei gespeichert und dann wieder von vorn gefüllt... Die Primzahlen, die ich zum Testen habe sind in nem anderen Array...

Naja... Wie du meinst...
Bye Tom

*john 0

unskilled schrieb:

Du nimmst vector - vector hat meines erachtens aber eine max.größe und ist langsamer, weil er ständig neuen Speicher alloziiert

Schon einmal das Programm angeschaut?
Offensichtlich nicht, denn dann wäre Dir aufgefallen, daß eben dies NICHT der Fall ist. std::vector<>::reserve ist die entscheidende Stelle.

unskilled schrieb:

mein Array hingegen ist statisch, wird immer, wenn es voll ist in ne Datei gespeichert und dann wieder von vorn gefüllt... Die Primzahlen, die ich zum Testen habe sind in nem anderen Array...

Aha, zum Testen muß man alle (jedenfalls von 3 bis Wurzel(Max)) schon errechneten Primzahlen benutzen, es bringt ergo gar nichts sie auszulagern und man braucht auch kein zweites Array.

P.S. Ein lauffähiges Programm hast Du nicht gepostet, sondern nur verschiedene Schleifen, oder hast Du mehrere Namen benutzt?

Edit: Teil gelöscht anderes Posting geändert.
Edit: Weitere Anwort auf Frage angefügt

unskilled

Hmm... Aber auch so passen eben 'nur' 10Millionen Elemente in dein Array - dann wird alles kopiert (nach 20 Mil. noch ma das gleiche, dann bei 40 wieder etc...)... Bevor du fragst: Ja, ich hab das für die Schule für nen Projekt geschrieben gehabt um irgend was über die Differenzen zwischen den Primzahlen (Primzahlzwillinge etc) darstellen zu können... Weiß nicht mehr, wie weit ich gekommen war aber hatte vor kurzem die Datei ma wieder gefunden - die war 2,5GB und da standen nur Primzahlen drin ^^ Also brauch ich 2 Arrays - du für deine Belange nicht, aber ich brauchte sie damals eben : P
"P.S. Ein lauffähiges Programm hast Du nicht gepostet, sondern nur verschiedene Schleifen, oder hast Du mehrere Namen benutzt?"
Nein - nur die beiden Schleifen... Das Programm hatte noch viel anderes drin (Statistiken, ...) - das hätte hier alles nciht reingehört und so und so hab ich es nur wegen des Algorithmus gepostet...

was mir gerad noch einfällt: Mein Array mit Primzahlen, die ich als Teiler verwende, enthält keine 2... Deins schon... Du prüfst also jede ungerade Zahl darauf, ob 2 ein Teiler ist

Byebye

*john 0

unskilled schrieb:

Hmm... Aber auch so passen eben 'nur' 10Millionen Elemente in dein Array - dann wird alles kopiert (nach 20 Mil. noch ma das gleiche, dann bei 40 wieder etc...)...

Die Größe der Reservierung muß man entsprechend anpassen. Man findet unter den n ersten Zahlen etwas mehr als n/ln(n) Zahlen, wenn als Obergrenze 1.2*n/ln(n) nimmt ist man wohl auf der sicheren Seite. Also kann man auch

primes.reserve(std::floor(1.2*max/std::log(max)));

setzen, so daß man ausreichend Speicher ohne Reallokation bereitstellt.

Bevor du fragst: Ja, ich hab das für die Schule für nen Projekt geschrieben gehabt um irgend was über die Differenzen zwischen den Primzahlen (Primzahlzwillinge etc) darstellen zu können... Weiß nicht mehr, wie weit ich gekommen war aber hatte vor kurzem die Datei ma wieder gefunden - die war 2,5GB und da standen nur Primzahlen drin ^^ Also brauch ich 2 Arrays - du für deine Belange nicht, aber ich brauchte sie damals eben : P

Ok, so kann man das nachvollziehen.

was mir gerad noch einfällt: Mein Array mit Primzahlen, die ich als Teiler verwende, enthält keine 2... Deins schon... Du prüfst also jede ungerade Zahl darauf, ob 2 ein Teiler ist

Der Index für die Prüfung (test) wird immer auf 1 gesetzt, und die 2 steht an Stelle 0.