Primzahlen ausgeben

Konrad Rudolph schrieb:

prime schrieb:

wobei du nur von 1 - 7 überprüfen musst, denn 8 und 9 sind Vielfache von 2 und 3 ...

Du hast offensichtlich nicht verstanden, was eine Primzahl ist.

Entweder bist du zu voreilig und hast den Nachpost nicht gelesen oder ich hab nicht verstanden was eine Primzahl ist.

Konrad Rudolph

prime schrieb:

Konrad Rudolph schrieb:

prime schrieb:

wobei du nur von 1 - 7 überprüfen musst, denn 8 und 9 sind Vielfache von 2 und 3 ...

Du hast offensichtlich nicht verstanden, was eine Primzahl ist.

Entweder bist du zu voreilig und hast den Nachpost nicht gelesen oder ich hab nicht verstanden was eine Primzahl ist.

Das Nachposting macht's nicht besser. Es reicht einfach nicht, die Zahlen 2–7 zu prüfen. Man muss jeden möglichen Teiler prüfen.

Eine Primzahl ist ja als Zahl definiert, die nur durch sich selbst und durch 1 teilbar ist. Nach Deinem Code würde die Definition lauten „eine Zahl, die nicht durch die Zahlen 2–7 teilbar ist.“

Und ich liefere auch gleich ein Gegenbeispiel: Dein Code würde ausgeben, dass 121 eine Primzahl ist, dabei ist 121 durch 11 teilbar.

liggi1998

ich hab auch mal so ein Programm geschrieben. Hier ist meine Version(hat zwar noch einige Bugs)

#include <iostream>

using namespace std;

bool istPrimzahl(int zahl)
{
     int i;
     float temp;
     for(i = 2; i<zahl-1; i++)
     {
           temp = zahl%i;
           if (temp == 0) return false;
     };
     return true;
};

int main(int argc, char *argv[])
{
    int z, bis;
    bool test;
    cout << "Geben sie ein bis wohin sie die Primzahlen angezeickt bekommen wollen:" << endl;
    cin >> bis;
    z = 3;
    while(z!=bis)
    {
         test = istPrimzahl(z);
         if (test == true) cout << z << endl;
         z++;
    };
    system("PAUSE");
    return EXIT_SUCCESS;
}

Auch EXIT_SUCCESS ist in stdlib definiert.-Also "#include <cstdlib>".

Mein Code denn ich gestern gepostet habe, hat übrigens noch einen Fehler:

for(int teiler=2;teiler<=grenzwert;teiler++)

und nicht

for(int teiler=2;teiler<=9;teiler++)

Vollständig und richtig also:

#include <iostream>

int main(void)
{
	std::cout<<"Grenzwert: ";
	int grenzwert;
	std::cin>>grenzwert; fflush(stdin);

	//Jede Ganzzahl zwischen 2 und dem benutzerdefinierten Grenzwert koennte eine Primzahl sein,
	//weshalb in der Folge jede durchgetestet wird.
	for(int potenzielle_primzahl=2;potenzielle_primzahl<=grenzwert;potenzielle_primzahl++)
	{
		bool ist_primzahl=true;

		//Ist die potenzielle Primzahl auch durch eine andere Zahl als 1 und sich selbst teilbar?
		for(int teiler=2;teiler<=grenzwert;teiler++)
		{
			if(potenzielle_primzahl%teiler==0&&potenzielle_primzahl!=teiler)
				ist_primzahl=false;
		}

		if(ist_primzahl==true)
			std::cout<<potenzielle_primzahl<<std::endl;
	}

	std::cin.get();
}

unskilled

Ich hab so was auch mal geschrieben - zwar schon ewig her aber es ist toll
Wobei man Primzahlen besser nur auf die Teilbarkeit durch Primzahlen prüft - ist schneller, als durch jede Zahl wieder versuchen zu teilen ^^

So ist übrigens sehr viel schneller, als deine Variante:

unsigned int to = 1;
for (__int64 i = 3; i < 1347890000000; i+=2)
	{
		if (to*to <= i)
			++to;
		bool isprim = true;
		unsigned __int32 teil = 0;
		while ((isprim) && (teiler[teil] < to))
			{
				if (i%teiler[teil] == 0)
					{
						isprim = false;
					}
				teil++;
			}
//....
	}

teiler[....] ist nen Array von Primzahlen - somit wird bei jeder Zahl also nur geguckt, ob sie durch eine Primzahl teilbar ist...

Heinzelotto

die primzahlen im array müssen aber auch erstmal berechnet werden. Wie machst du das dann? noch ein array mit noch kleineren Primzahlen? aber wie hast du das dann berechnet?

Das mit dem array ist prinzipiell eine gute idee, aber nicht so gut, wenn man nur begrenzten Speicher hat. Also entweder schnelles Rechnen, oder geringer Speicherverbrauch.

unskilled

so:

unsigned __int32 teiler[90100];
unsigned __int32 a = 0;
unsigned __int32 to = 1;

for (unsigned __int32 j = 3; j < 1160990; j+=2)
	{
		if (to*to <= j)
			++to;
		bool isprim = true;
		unsigned __int32 teil = 3;
		while ((isprim) && (teil < to))
			{
				if (j%teil == 0)
					{
						isprim = false;
					}
				teil += 2;
			}
		if (isprim)
			teiler[a++] = j;
	}

Naja.. Speicher... nicht mal 352KB... Also für das Array mit den Primzahlen (90100*32/8/1024 == 351,...)
Und da das Prog den PC so und so zu ~100% auslastet ists auch egal, wie viel RAM ungenutzt bleibt - nebenbei kann man eh nix mehr machen ;o) (na k - wenn man 2 CPUS hat dann geht das schon - aber mal ehrlich... Was ist das heut zu Tage schon noch?

Ciao : )

Heinzelotto

naja, das war ein recht schlechtes Beispiel, um zu zeigen, dass man manchmal vor der Wahl zwischen Speicherverbrauch und Rechenzeit steht, aber überleg mal, was passieren würde, wenn man nicht die Primzahlen unter 2^32-1, sondern z.B. die Primzahlen unter 2^2000000 ausrechnen wollte. Dann wären das andere Größenordnungen als einige kilobyte

Kann einfach mal einer die Primzahlen hochladen, dann muss sie nicht jeder immer wieder ausrechnen.

unskilled

In der Größenordnung könntest du auch so nichts mehr mit den Mitteln anfangen... Du müsstest dir ne eigene Zahlenklasse schreiben und dort das addieren, multiplizieren und dividieren implementieren... btw würde ich gerade in solchen Größenordnungen diese Lösung bevorzugen!

/edit:
Auch dann ist es noch schneller - man muss diese Primzahlen eben nur Stück für Stück speichern und wieder durch andere überschreiben und wieder neu berechnen...

bb

(Es ging ursprünglich nicht darum einen möglichst "schlauen" Algorithmus zu implementieren, sondern einen möglichst einfachen in Bezug auf das Verständnis.)

*john 0

So, nun auch mein Programmcode zu diesem Thema.

Ein paar einleitende Worte zu Mathematik.
Als erstes braucht man nur ungerade Zahlen zu testen, alle gerade sind mindestens in den Primfaktor 2 zu zerlegen und damit definitiv keine Primzahl. Es ist nur sinnvoll Primzahlen zum Testen zu verwenden, und man braucht nur die zu nehmen die kleiner oder gleich der Wurzel der zu testenden Zahl sind. (p*p <= i) Wenn wir einen Primfaktor gefunden haben, können wir den Test auf Teilbarkeit abbrechen, da die Zahl nicht prim ist.

Es wird der Datentyp long long verwendet, was nicht ISO konform ist. Wenn es nicht funktioniert durch long ersetzen.

#include <ostream>
#include <iostream>
#include <vector>

int main() {
        std::size_t const       MAX_ELEM = 10000000;
        long long const         max =      10000001;

        std::vector<long long>  primes;
        primes.reserve(MAX_ELEM);

        primes.push_back(2);
        primes.push_back(3);

        // Edit:  Index angepaßt
        // Sorry: Man sollte den Code nicht auf der Webseite schreiben
        for (long long i = 5; i != max; i+=2) {
                long long test (1);
                bool p (true);

                while (p && ((primes[test]*primes[test]) <= i)) {
                        if (0 == (i % primes[test++])) {
                                p = false;
                                break;
                        }
                }
                if (true == p) {
                        primes.push_back(i);
                }
        }

        std::cout << primes.size() << " Primzahlen gefunden\n";
        std::cout << "Alle Primzahlen bis " << max << "\n";
        for (std::vector<long long>::const_iterator it(primes.begin()), en(primes.end()); it != en; ++it) {
                std::cout << *it << "\n";
        }
}

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.