Primzahlen ermitteln

[Marthog]

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.

[SG1]

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ß.

[jkhsjdhjs]

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

[DirkB]

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.

[jkhsjdhjs]

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.

[SeppJ]

jkhsjdhjs schrieb:

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

Finger weg von Webtutorials, besonders deutschsprachigen! Finger weg von Galileo Computing! Und jetzt darfst du raten, was der Ratschlag zu deutschsprachigen Webtutorials basierend auf einem Buch von Galileo Computing ist.

Kaum etwas ist so schlecht für einen selbst, wie ein schlechter Lehrer, von dem man Falsches lernt. Guck mal in meine Signatur und im Thread "Linkliste für Neulinge", wo du besseres Lehrmaterial findest.

[jkhsjdhjs]

SeppJ schrieb:

jkhsjdhjs schrieb:

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

Finger weg von Webtutorials, besonders deutschsprachigen! Finger weg von Galileo Computing! Und jetzt darfst du raten, was der Ratschlag zu deutschsprachigen Webtutorials basierend auf einem Buch von Galileo Computing ist.

Kaum etwas ist so schlecht für einen selbst, wie ein schlechter Lehrer, von dem man Falsches lernt. Guck mal in meine Signatur und im Thread "Linkliste für Neulinge", wo du besseres Lehrmaterial findest.

Ok, Danke

EDIT: Habe mir jetzt folgenden Artikel mal angeschaut:
http://www.c-plusplus.net/forum/155739

Und habe gedacht, dass ich den TCHAR desktop doch mit dem Dateinamen zusammenfügen kann.

#include <string>
string s;
s = TCHAR("desktop") + "\\Primzahlen.txt";

Dabei bekomm ich auch keine Fehler.

Nur hierbei

f.open(s, ios::out);

bekomme ich dann folgenden Fehler:
**1>c:\users\****\documents\visual studio 2008\projects\aufgabe 3\aufgabe 3\aufgabe 3.cpp(88) : error C2664: 'void std::basic_fstream<_Elem,_Traits>::open(const wchar_t ,std::ios_base::openmode,int)': Konvertierung des Parameters 1 von 'std::string' in 'const wchar_t ' nicht möglich

Ich denke mal, dass ich keinen string als Dateipfad nehmen darf, oder?

EDIT2: Könnte es eigentlich Probleme geben, wenn ich ein ä,ö oder ü in meinem Benutzernamen habe?

EDIT3: Ok, habe jetzt echt keinen Plan mehr, hier mein jetziger Stand. Im Programm hat sich eigentlich nix geändert. Die Datei wird jetzt in C:\ erstellt, will sie aber auf dem Desktop haben. Beim Dateien verschieben darf man auch nicht einfach %userprofile% nehmen, also ich hab echt kp mehr.

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

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

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];
	fstream f;

	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 (maximal 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 ent-\nschieden!\n";
			cout<<"Bitte geben Sie nun ein, bis zur wie vielten Primzahl ermittelt werden soll\n(maximal 250.000)!"<<endl;
			cout<<"maximale Primzahl: ";
			cin>>numberOfPrimes;
			do {
				cout<<"Sollen die gefunden Primzahlen in die Datei Primzahlen.txt auf dem Desktop ge-\nschrieben 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...";

			// 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
				}
			}

			cout<<"Fertig!\n";

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

			cout<<"Ausgabe der Primzahlen in 3 Sekunden...";
			Sleep(3000);
			cout<<endl;

			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;
}

[jkhsjdhjs]

Habe jetzt noch folgendes hinter SHGetFolderPath geschrieben:

for (int i = 0; i <= MAX_PATH; i++) {
					if (desktop[i] == 52428 && A == 0 || desktop[i] == 0 && A == 0) {
						desktop	[i] = 92;
						desktop	[i + 1] = 80;
						desktop	[i + 2] = 114;
						desktop	[i + 3] = 105;
						desktop	[i + 4] = 109;
						desktop	[i + 5] = 122;
						desktop	[i + 6] = 97;
						desktop	[i + 7] = 104;
						desktop	[i + 8] = 108;
						desktop	[i + 9] = 101;
						desktop	[i + 10] = 110;
						desktop	[i + 11] = 46;
						desktop	[i + 12] = 116;
						desktop [i + 13] = 120;
						desktop [i + 14] = 116;
						A = 1;
					}
				}

Damit fülle ich das TCHAR array dann einzeln mit den Zeichen für "\Primzahlen.txt".
Wenn ich dann

wcout<<desktop;

mache, wird der Pfad auch korrekt angezeigt, nur aus irgendeinem Grund wird auf dem Desktop keine Datei angelegt. Auch wenn ich das Programm als Administrator ausführe nicht.
Kann mir da jemand weiterhelfen?

Und an alle Moderatoren/Administratoren: Sry für den Doppelpost, aber wenn ich nur editiert hätte, hätte ja nie jemand gesehn, dass ich noch ne Frage habe.

EDIT: Bei f.open habe ich natürlich auch desktop anstatt C:\\Primzahlen.txt hingeschrieben. Zur besseren Übersicht am besten hier nochmal der komplette Programmcode:

// 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, A = 0;
	char datei, choice;
	TCHAR desktop [MAX_PATH];
	fstream f;

	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 (maximal 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 ent-\nschieden!\n";
			cout<<"Bitte geben Sie nun ein, bis zur wie vielten Primzahl ermittelt werden soll\n(maximal 250.000)!"<<endl;
			cout<<"maximale Primzahl: ";
			cin>>numberOfPrimes;
			do {
				cout<<"Sollen die gefunden Primzahlen in die Datei Primzahlen.txt auf dem Desktop ge-\nschrieben 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...";

			// 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
				}
			}

			cout<<"Fertig!\n";

			if (datei == 'j' || datei == 'J') {
				cout<<"Datei wird geschrieben...";
				SHGetFolderPath(NULL,CSIDL_DESKTOPDIRECTORY,NULL,SHGFP_TYPE_CURRENT,desktop);
				for (int i = 0; i <= MAX_PATH; i++) {
					if (desktop[i] == 52428 && A == 0 || desktop[i] == 0 && A == 0) {
						desktop	[i] = 92;
						desktop	[i + 1] = 80;
						desktop	[i + 2] = 114;
						desktop	[i + 3] = 105;
						desktop	[i + 4] = 109;
						desktop	[i + 5] = 122;
						desktop	[i + 6] = 97;
						desktop	[i + 7] = 104;
						desktop	[i + 8] = 108;
						desktop	[i + 9] = 101;
						desktop	[i + 10] = 110;
						desktop	[i + 11] = 46;
						desktop	[i + 12] = 116;
						desktop [i + 13] = 120;
						desktop [i + 14] = 116;
						A = 1;
					}
				}
				f.open(desktop, ios::out);
				for (count = 0; count <= numberOfPrimes - 1; count++) {
					f<<count + 1<<".Primzahl: "<<Prim [count]<<endl;
				}
				f.close();
				cout<<"Fertig!\n";
			}

			cout<<"Ausgabe der Primzahlen in 3 Sekunden...";
			Sleep(3000);
			cout<<endl;

			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;
}

[DirkB]

Du solltest dich mal mit den Unterschieden zwischen std:string und char (wchar, TCHAR) befassen.

Und dir auch mal Funktionen wie strcat (bzw. entsprechende Funktion für wchar) ansehen.

Deine Anhängeroutine ist ziemlich übel.
Es reicht aus, wenn du das Ende findest und danach brauchst du keine Schleife mehr.
Nebenbei kannst du statt 46 auch '.' schreiben. Ebenso für 116 't' .....

[jkhsjdhjs]

Hi DirkB,

Danke für deine Antwort! Ich werde mir die Funktionen mal ansehen, warscheinlich werden wir sie in naher Zukunft auch in der Schule durchnehmen.

Aber könntest du das Programm mal auf deinem PC aufprobieren? Weil ich glaube irgendwie, dass es daran liegt, dass ich ein ö im Benutzernamen habe. Bei wcout wird das ö nämlich auch als geteilt-durch-Zeichen angezeigt.