3. Primzahlen ermitteln

Primzahlen ermitteln

  • K

    Was fuer eine schule ist das? Und in welchem jahr bist du?

    Greets

    0
  • J

    @Kellerautomat: Danke, ich werds mir heute mal durchlesen und dich nochmal anschreiben wenn ich was nicht verstehe.

    @kamelkacke: ein berufliches Gymnasium, bin in der 12ten

    EDIT: @Kellerautomat: Ja, hab alles verstanden wasdu erklärt hast, werde das Programm noch etwas abändern, da es die Aufgabe war, zuerst alle Primzahlen in einem Array zu speichern und danach auszugeben.
    Danke nochmals 😉

    EDIT2: @Kellerautomat: Habs grad geändert und muss sagen, die Methode geht ja sau schnell. Mein PC (Core 2 Duo @ 3,6GHz) braucht nun nur noch ne halbe Sekunde um alle zu berechnen 😃
    Nur die Ausgabe dauert halt ewig ^^

    EDIT3: Hier das fertige Programm:

    // Aufgabe 3.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//

#include "stdafx.h"
#include <conio.h>
#include <iostream>

using namespace std;

bool isPrime(unsigned n) {
	if(n < 2) { // zahlen < 2 sind keine primzahlen
        return false;
	}

	for(unsigned i = 2; i * i <= n; i++) { // fuer alle zahlen 2, 3, ..., wurzel(n) - 1, wurzel(n) ...
        if(n % i == 0) // ... wenn n durch i teilbar ist, ...
            return false; // ... dann haben wir keine primzahl
	}

    return true; // wenn n durch keine der zahlen teilbar ist, dann haben wir eine primzahl gefunden
}

int _tmain(int argc, _TCHAR* argv[]) {

	int Prim [100000], numberOfPrimes, count;

	cout<<"Dieses Programm ermittelt und gibt Primzahlen aus!";
	cout<<"\n\nBitte geben Sie nun ein, bis zur wie vielten Primzahl ermittelt werden soll (maximal 100.000)!"<<endl;
	cout<<"maximale Primzahl: ";
	cin>>numberOfPrimes;
	cout<<"\nErmittlung laeuft...";

    // count zaehlt die anzahl der primzahlen, die wir schon gefunden haben
    // n zaehlt einfach der reihe nach solange zahlen hoch, bis wir fertig sind
    for(unsigned count = 0, n = 0; count != numberOfPrimes; n++) // solange wir noch nicht genug primzahlen haben ...
		if(isPrime(n)) { // ... wenn die aktuelle zahl eine primzahl ist ...
			Prim [count] = n; //... wird sie im array gespeichert ...
            count++; // ... und die anzahl gefunder primzahlen um 1 erhöht
        }

	for (count = 0; count <= numberOfPrimes - 1; count++) {
		cout<<endl<<count + 1<<". Primzahl: "<<Prim [count];
	}

	cout<<"\n\nDruecken Sie eine beliebige Taste zum Beenden...";
	_getch();

	return 0;
}

    Nur wieso kannst du bei Primzahlermittlung einfach i * i rechnen? Kann man sich dann dennoch 100% sicher sein, dass die Primzahlen stimmen?

    0

  • Hallo,

    es reicht bis zur Wurzel von n, d.h. sqrt(n), zu rechnen~~, da alles, was darüber ist, keine Primzahl von n mehr sein kann (da der Rest-Faktor dann ja kleiner als 2 wäre)~~. Da aber die Wurzelberechnung langsam ist (und man zu Fließkommazahlen bei der Standardfunktion konvertieren müßte), ist es einfacher den Term "i <= sqrt(n)" zu "i * i <= n" umzuformen (denn für positive x und y gilt: wenn "x <= y" dann "x * x <= y * y").

    Man muß aber aufpassen, den Wertebereich bei "i * i" nicht zu überschreiten, d.h. bei 4 Byte Integer dürfte i nur bis max. 65535 (= 2^16 - 1) laufen, damit die Ungleichung stimmt!!!

    Edit: da habe ich gestern abend 2 Sachen durcheinander gebracht (nach der Arbeit sollte man nicht mehr posten 😉
    Ich hatte zuerst die Optimierung auf "i <= n/2" im Kopf und dann erst gemerkt, daß ja schon die Optimierung auf "sqrt(n)" im Code ist.

    0
  • J

    Th69 schrieb:

    Hallo,

    es reicht bis zur Wurzel von n, d.h. sqrt(n), zu rechnen, da alles, was darüber ist, keine Primzahl von n mehr sein kann (da der Rest-Faktor dann ja kleiner als 2 wäre). Da aber die Wurzelberechnung langsam ist (und man zu Fließkommazahlen bei der Standardfunktion konvertieren müßte), ist es einfacher den Term "i <= sqrt(n)" zu "i * i <= n" umzuformen (denn für positive x und y gilt: wenn "x <= y" dann "x * x <= y * y").

    Man muß aber aufpassen, den Wertebereich bei "i * i" nicht zu überschreiten, d.h. bei 4 Byte Integer dürfte i nur bis max. 65535 (= 2^16 - 1) laufen, damit die Ungleichung stimmt!!!

    Ansonsten werden die Primzahlen falsch berechnet und stimmen nicht mehr, oder wie?
    Also ich habe die Primzahlen bis zur 100.000ten Primzahl berechnet (1.299.709) und habe diese und noch ein paar darüberliegende auf einer Internetseite überprüft und die haben alle gestimmt. Und bei 1.000.000 hat i 65535 ja schon längt überschritten. Oder sehe ich das falsch?

    0
  • N

    jkhsjdhjs schrieb:

    Th69 schrieb:

    Hallo,

    es reicht bis zur Wurzel von n, d.h. sqrt(n), zu rechnen, da alles, was darüber ist, keine Primzahl von n mehr sein kann (da der Rest-Faktor dann ja kleiner als 2 wäre). Da aber die Wurzelberechnung langsam ist (und man zu Fließkommazahlen bei der Standardfunktion konvertieren müßte), ist es einfacher den Term "i <= sqrt(n)" zu "i * i <= n" umzuformen (denn für positive x und y gilt: wenn "x <= y" dann "x * x <= y * y").

    Man muß aber aufpassen, den Wertebereich bei "i * i" nicht zu überschreiten, d.h. bei 4 Byte Integer dürfte i nur bis max. 65535 (= 2^16 - 1) laufen, damit die Ungleichung stimmt!!!

    Ansonsten werden die Primzahlen falsch berechnet und stimmen nicht mehr, oder wie?
    Also ich habe die Primzahlen bis zur 100.000ten Primzahl berechnet (1.299.709) und habe diese und noch ein paar darüberliegende auf einer Internetseite überprüft und die haben alle gestimmt. Und bei 1.000.000 hat i 65535 ja schon längt überschritten. Oder sehe ich das falsch?

    Nein, i ist dann ja bei sqrt(1000000) maximal.
    Und wenn ein Überlauf stattfindest merkst du das schon, dein Programm beendet sich nämlich nicht mehr.
    Und warum speicherst du die Primzahlen? Gib sie doch direkt aus?

    0
  • J

    Nathan schrieb:

    jkhsjdhjs schrieb:

    Th69 schrieb:

    Hallo,

    es reicht bis zur Wurzel von n, d.h. sqrt(n), zu rechnen, da alles, was darüber ist, keine Primzahl von n mehr sein kann (da der Rest-Faktor dann ja kleiner als 2 wäre). Da aber die Wurzelberechnung langsam ist (und man zu Fließkommazahlen bei der Standardfunktion konvertieren müßte), ist es einfacher den Term "i <= sqrt(n)" zu "i * i <= n" umzuformen (denn für positive x und y gilt: wenn "x <= y" dann "x * x <= y * y").

    Man muß aber aufpassen, den Wertebereich bei "i * i" nicht zu überschreiten, d.h. bei 4 Byte Integer dürfte i nur bis max. 65535 (= 2^16 - 1) laufen, damit die Ungleichung stimmt!!!

    Ansonsten werden die Primzahlen falsch berechnet und stimmen nicht mehr, oder wie?
    Also ich habe die Primzahlen bis zur 100.000ten Primzahl berechnet (1.299.709) und habe diese und noch ein paar darüberliegende auf einer Internetseite überprüft und die haben alle gestimmt. Und bei 1.000.000 hat i 65535 ja schon längt überschritten. Oder sehe ich das falsch?

    Nein, i ist dann ja bei sqrt(1000000) maximal.
    Und wenn ein Überlauf stattfindest merkst du das schon, dein Programm beendet sich nämlich nicht mehr.
    Und warum speicherst du die Primzahlen? Gib sie doch direkt aus?

    Achso, ok. Na dann ist das ja nicht der Fall.

    Und die Zahlen speicher, weil ich eigentlich für die Schule die Aufgabe mache und wir da grad das Thema Arrays haben und diese Aufgabe dazu machen sollten.
    Eigentlich sollte das Programm auch nur die Primzahlen bis 20 ermitteln, aber ich fand das halt ein bischen öde, da das Programm bei jedem Start immer wieder das selbe macht und keine Benutzereingaben erfordert.

    0
  • ?

    Th69 schrieb:

    es reicht bis zur Wurzel von n, d.h. sqrt(n), zu rechnen, da alles, was darüber ist, keine Primzahl von n mehr sein kann (da der Rest-Faktor dann ja kleiner als 2 wäre).

    Stimmt nicht ganz, das ist nicht die Begründung, um nur bis zur Wurzel zu rechnen. Es gibt auch Primfaktoren größer als die Wurzel und der Restfaktor wird auch nicht kleiner als 2. Gegenbeispiel: 35 = 7*5 , 7 ist größer als sqrt(35)≈5,9 und 5>2.

    jkhsjdhjs schrieb:

    Ansonsten werden die Primzahlen falsch berechnet und stimmen nicht mehr, oder wie?

    Nein, nicht falsch nur unnötig. Bis zur Wurzel von n zu rechnen ist eine Optimierung und beschleunigt die Ausführung ganz erheblich.

    Wir prüfen ja
    if(n % i == 0)
    und hätten in dem Fall einen Teiler i gefunden, können also false zurückgeben weil n damit keine Primzahl ist.

    Wenn es also einen Teiler i gibt, gilt n = i*j für eine andere Zahl j. Ein Teiler i kann selbstverständlich größer als die Wurzel von n sein, aber in dem Fall wäre der andere Faktor j kleiner als die Wurzel. Da wir aufsteigend alle Zahlen in der Schleife prüfen, finden wir stets die kleineren Faktoren zuerst. Der Punkt in dem beide hypothetischen Teiler gleich groß sind ist genau bei der Wurzel(n) erreicht und wir müssen größere Zahlen nicht mehr prüfen: Wären sie Teiler, hätten wir einen anderen, kleineren, Teiler schon vorher entdeckt.

    0

  • Mich wundert es ein wenig, dass noch niemand das Sieb des Eratosthenes erwähnt hat.

    Edit:
    Ah, weil die ersten n Primzahlen gefragt sind, und nicht alle Primzahlen bis n. Ergibt Sinn.

    0
  • M

    DocShoe schrieb:

    Mich wundert es ein wenig, dass noch niemand das Sieb des Eratosthenes erwähnt hat.

    Edit:
    Ah, weil die ersten n Primzahlen gefragt sind, und nicht alle Primzahlen bis n. Ergibt Sinn.

    Man kann das Sieb des Erastothenes auch für die ersten n Primzahlen anwenden, man muss dann halt nur suchen, bis das Array n Elemente enthält, während man sonst bis n alle Promzahlen überprüfen würde.
    Ich hätte das Sieb ja schon erwähnt, aber für die Schule, es scheint ja wirklich um grundlagen und simple Dinge zu gehen, reicht auch die andere Variante, hauptsache er versteht die Lösung auch.

    EDIT: Das overflow-Problem lässt sich doch einfach mit 64-bit-integern umgehen, bzw. so weit verschieben, dass man eh nicht mehr so lange sucht:
    Statt unsigned int benutze unsigned long long oder std::uint64_t

    0
  • S

    Marthog schrieb:

    DocShoe schrieb:

    Mich wundert es ein wenig, dass noch niemand das Sieb des Eratosthenes erwähnt hat.

    Edit:
    Ah, weil die ersten n Primzahlen gefragt sind, und nicht alle Primzahlen bis n. Ergibt Sinn.

    Man kann das Sieb des Erastothenes auch für die ersten n Primzahlen anwenden, man muss dann halt nur suchen, bis das Array n Elemente enthält, während man sonst bis n alle Promzahlen überprüfen würde.

    Und wie weit geht man dann jeweils mit dem Durchstreichen?

    0
  • J

    Ich hab mir das Sieb des Eratosthenes mal angeschaut und verstehe den Algorithmus soweit, ich werde es mal versuchen einzubauen. Danke 😉

    und @µ: Danke für deine ausführliche Antwort, habs kapiert 😉

    0
  • Mod

    SG1 schrieb:

    Und wie weit geht man dann jeweils mit dem Durchstreichen?

    Wir könnten natürlich Zahlentheorie benutzen und wissen, dass die Primzahldichte logarithmisch ist und dann eine sichere obere Grenze abschätzen. Oder wir machen es mit cleveren Algorithmen:

    #include <queue>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main()
{
  unsigned max_num_primes;
  cout << "Wie viele Primzahlen? ";
  cin >> max_num_primes;

  // Die 2 sparen wir uns mal bei der Rechnung:
  if (max_num_primes > 0)
    {
      cout << "2\t";
      unsigned num_primes_printed = 1;
      unsigned current_number = 3;

      std::priority_queue<pair<unsigned int, unsigned int>,
        vector< pair<unsigned int, unsigned int> >,
        greater< pair<unsigned int, unsigned int> >
        > 
        queue;

      while (num_primes_printed < max_num_primes)
        {
          if (queue.empty() || queue.top().first != current_number)
            {
              cout << current_number << '\t';
              ++num_primes_printed;
              queue.push(make_pair(current_number*current_number, current_number*2));
            }
          else
            {
              for(pair<unsigned int, unsigned int> top = queue.top();
                  top.first == current_number;
                  top=queue.top())
                {
                  queue.pop();
                  queue.push(make_pair(top.first + top.second, top.second));
                }              
            }
          current_number += 2;
        }
      cout << '\n';
    }
}

    (Ich wollte schon immer mal eine priority_queue prakitsch einsetzen 😋 )

    Erklärung:
    http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

    0
  • J

    Also bei mir hat sich herausgestellt, dass ich es nicht hinbekomme mit dem Sieb und wenn dann würde es wieder ellen lang werden. Deshalb hab ich jetzt mal das Programm, welches SeppJ gepostet hat ausprobiert. Doch leider meldet mit Visual C++ 2008 Fehler. Zuerst musste ich noch stdafx.h als Header einfügen, weil Visual C++ einen vorkompilierten Header braucht, aber dann waren da immer noch Fehler in queue.

    1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\queue(160) : error C2529: '_Pred': Verweis auf Verweis ungültig
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\queue(174) : error C2529: '_Pred': Verweis auf Verweis ungültig
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\queue(181) : error C2529: '_Pred': Verweis auf Verweis ungültig

    Deshalb bleibe ich besser bei der Methode mit dem Modulo Operator. Aber ich hätte dazu noch eine Frage:
    Kann ich die größe eines Arrays noch irgendwie auf 1.000.000 oder mehr erweitern? Weil wenn ich zum Beispiel die größe auf 500.000 setze, bekomme ich Stack overflow und was mit Für deiesen Bereich ist kein Quellcode verfügbar, noch bevor das Programm startet. Hat da jemand ne Idee bzw. ist das überhaupt möglich?

    0
  • S

    SeppJ schrieb:

    Erklärung:
    http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

    nice, danke!

    0
  • Mod

    jkhsjdhjs schrieb:

    Also bei mir hat sich herausgestellt, dass ich es nicht hinbekomme mit dem Sieb und wenn dann würde es wieder ellen lang werden. Deshalb hab ich jetzt mal das Programm, welches SeppJ gepostet hat ausprobiert. Doch leider meldet mit Visual C++ 2008 Fehler. Zuerst musste ich noch stdafx.h als Header einfügen, weil Visual C++ einen vorkompilierten Header braucht, aber dann waren da immer noch Fehler in queue.

    Das Programm sollte korrekt sein, du machst irgendwas falsch mit deiner IDE.

    http://ideone.com/PiJXnw

    Kann ich die größe eines Arrays noch irgendwie auf 1.000.000 oder mehr erweitern? Weil wenn ich zum Beispiel die größe auf 500.000 setze, bekomme ich Stack overflow und was mit Für deiesen Bereich ist kein Quellcode verfügbar, noch bevor das Programm startet. Hat da jemand ne Idee bzw. ist das überhaupt möglich?

    Keine Arrays benutzen. Solche großen Strukturen macht man doch sowieso mit vector.

    0
  • M

    SG1 schrieb:

    Und wie weit geht man dann jeweils mit dem Durchstreichen?

    Wieso durchstreichen? Während die traditionelle Methode, um zu überprüfen, ob die Zahl x eine Primzahl ist, x auf Teilbarkeit durch jede andere Zahl z überprüft, für die gilt z*z<=x, überprüft man hier nur, ob x durch die Primzahl p, für die gilt p*p <= x, teilbar ist. Da man von 0 anfängt, hat man alle Primzahlen, die kleiner als x sind, bereits gefunden.

    Sehr schnell ist auch das Sieb von Atkin. Das finde ich aber etwas zu kompliziert.

    0
  • S

    Marthog schrieb:

    SG1 schrieb:

    Und wie weit geht man dann jeweils mit dem Durchstreichen?

    Wieso durchstreichen?

    Weil meine Frage sich auf das Sieb des Eratosthenes bezog.

    Während die traditionelle Methode, um zu überprüfen, ob die Zahl x eine Primzahl ist, x auf Teilbarkeit durch jede andere Zahl z überprüft, für die gilt z*z<=x, überprüft man hier nur, ob x durch die Primzahl p, für die gilt p*p <= x, teilbar ist. Da man von 0 anfängt, hat man alle Primzahlen, die kleiner als x sind, bereits gefunden.

    Ach, sag bloß.

    0
  • J

    Habe mein Programm jetzt nochmal ausgebaut:
    - Es kann jetzt einzelne Zahlen auf Primzahlen überprüfen

    Wollte auch noch Dateispeicherung hinzufügen, jedoch funktioniert es nicht so ganz wie ich es will. Würde mich freuen, wenn jemand von euch mir sagen könnte wo der Fehler liegt.

    Visual C++ 2008 meint, dass vor der Zeichenfolge unten in der Schleife fehlen, jedoch glaub ich, dass ich wieder zu dumm war das hinzubekommen ^^

    // Aufgabe 3.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//

#include "stdafx.h"
#include <conio.h>
#include <iostream>
#include <fstream>
#include <shlobj.h>

using namespace std;

bool isPrime(unsigned n) {
    if(n < 2) { // zahlen < 2 sind keine primzahlen
        return false;
    }

    for(unsigned i = 2; i * i <= n; i++) { // fuer alle zahlen 2, 3, ..., wurzel(n) - 1, wurzel(n) ...
        if(n % i == 0) // ... wenn n durch i teilbar ist, ...
            return false; // ... dann ist es keine primzahl
    }

    return true; // wenn n durch keine der zahlen teilbar ist, dann haben wir eine primzahl gefunden
}

int _tmain(int argc, _TCHAR* argv[]) {

	__int64 unsigned n;
	int Prim [250000], numberOfPrimes, count;
	char datei, choice;
	TCHAR desktop[MAX_PATH];

	cout<<"Dieses Programm ermittelt und gibt Primzahlen aus!\n\n\n";
	cout<<"Bitte waehlen Sie:"<<endl;
	cout<<"a) Zahl auf Primzahl ueberpruefen"<<endl;
	cout<<"b) Primzahlen bis zu einer bestimmen Primzahl ermitteln"<<endl;
	do {
		cout<<"Bitte geben Sie a oder b ein: ";
		cin>>choice;

		if (choice == 'a' || choice == 'A') {
			cout<<"\nSie haben sich fuer Zahl auf Primzahl ueberpruefen entschieden!"<<endl;
			cout<<"Bitte geben Sie eine Zahl ein (max. 2,5 Mrd.): ";
			do {
				cin>>n;
				if (n > 2500000000) {
					cout<<"Bitte geben Sie zur Ueberpruefung maximal 2,5 Mrd. ein:";
				}
			} while (n > 2500000000);
			if (isPrime(n)) {
				cout<<n<<" ist eine Primzahl!"<<endl;
			}
			else {
				cout<<n<<" ist KEINE Primzahl!"<<endl;
			}
		}

		else if (choice == 'b' || choice == 'B') {
			cout<<"\nSie haben sich fuer Primzahlen bis zu einer bestimmten Primzahl ermitteln\n";
			cout<<"Bitte geben Sie nun ein, bis zur wie vielten Primzahl ermittelt werden soll (maximal 100.000)!"<<endl;
			cout<<"maximale Primzahl: ";
			cin>>numberOfPrimes;
			do {
				cout<<"Sollen die gefunden Primzahlen in eine Datei auf dem Desktop geschrieben werden? (j oder n): ";
				cin>>datei;
				if (datei != 'n' && datei != 'N' && datei != 'j' && datei != 'J') {
					cout<<"\nBitte wiederholen Sie Ihre Eingabe! Bitte verwenden Sie nur j oder n als Antwort!\n\n";
				}
			} while (datei != 'n' && datei != 'N' && datei != 'j' && datei != 'J');

			cout<<"\nErmittlung laeuft...\n";

			// count zaehlt die anzahl der primzahlen, die wir schon gefunden haben
			// n zaehlt einfach der reihe nach solange zahlen hoch, bis wir fertig sind
			for(unsigned count = 0, n = 0; count != numberOfPrimes; n++) { // solange wir noch nicht genug primzahlen haben ...
				if(isPrime(n)) { // ... wenn die aktuelle zahl eine primzahl ist ...
					Prim [count] = n; //... wird sie im array gespeichert ...
					count++; // ... und die anzahl gefunder primzahlen um 1 erhöht
				}
			}

			if (datei == 'j' || datei == 'J') {
				SHGetFolderPath(NULL,CSIDL_DESKTOPDIRECTORY,NULL,SHGFP_TYPE_CURRENT,desktop);
				fstream f;
				f.open(desktop"\\Primzahlen.txt", ios::out);
				for (count = 0; count <= numberOfPrimes - 1; count++) {
					f<<count + 1<<".Primzahl: "<<Prim [count]<<endl;
				}
				f.close();
			}

			for (count = 0; count <= numberOfPrimes - 1; count++) {
				cout<<endl<<count + 1<<". Primzahl: "<<Prim [count];
		    }
		}
	} while (choice != 'a' && choice != 'A' && choice != 'b' && choice != 'B');

	cout<<"\n\nDruecken Sie eine beliebige Taste zum Beenden...";
	_getch();

    return 0;
}

    Das mit den Dateioperation hab ich von folgender Seite:
    http://www.willemer.de/informatik/cpp/fileop.htm

    0
  • ?

    Da du nicht angibst, wo VS meckert nehme ich mal n, dass es Zeile 85 ist.

    Bevor du Dateinamen zusammen bastelst, solltest du erstmal fit in der Stringverarbeitung sein. Und auch den Unterschied zwischen den verschiedenen Arten kennen.

    Lass das mit dem desktop weg, dann sollte das auch klappen.

    0
  • J

    Ja, du hast recht, es ist Zeile 85. Sry, dass ich das nicht angegeben hab.

    Habe es jetzt mal ohne desktop laufen lassen, frage mich nur, wo er jetzt die Datei gespeichert hat. Ich nehme mal an er hat gar keine erstellt, da ich dem Programm nicht gesagt hab, dass es eine erstellen soll, oder reicht da open?

    Und ich frage mich wieso es vorher nicht funktioniert hat, da ich doch mit SHGetFolderPath den Desktop-Ordner ausgelesen hab.

    0
Anmelden zum Antworten