Primzahlen ermitteln

[jkhsjdhjs]

Danke für deinen Hinweis.

Ich habe mein Programm jetzt auch dahingehend geändert, dass man nun am Anfang festlegen kann, bis zur wievielten Primzahl ermittelt werden soll.

Zu den for-Schleifen. Ich kann mit for Schleifen arbeiten und weiß wie sie funktionieren bzw. was sie machen. Jedoch komme ich mit While Schleifen einfach besser klar und verwende for-Schleifen deshalb nur in einfachen Fällen. Meistens ändere ich meine Programme dann aber noch, wenn sie funktionieren, zu for-Schleifen, wo es möglich ist. Aber ich finde hier in dem Fall keinen mit ersichtlichen Weg die While Schleife durch eine for-Schleife zu ersetzen.

[berniebutt]

Eine while-Schleife ist hier besser geeignet als eine for-Schleife, da die Anzahl Duchläufe nicht bekannt ist.
Kleiner Trick: mache eine Endlosschleife und beende diese sobald die gewünschte Anzahl Primzahlen gefunden ist, etwa so;

int zaehler = 0;
while (0 < 1)
{
   // Primzahlen suchen und Zähler aufaddieren --> zaehler++ 
   if (zaehler == 20) break;
}

[Sone]

while (0 < 1)

Die Bedingung ist doch Blödsinn. Nimm gleich true .

[Bashar]

Sone schrieb:

while (0 < 1)

Die Bedingung ist doch Blödsinn. Nimm gleich true .

Das gabs in FORTRAN wahrscheinlich noch nicht ... :|

[jkhsjdhjs]

Also mein Programm sieht jetzt wie folgt aus:

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

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

using namespace std;

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

	int Prim [100001], i = 0, maxPrim;
	float y, k = 1, x = 2;
	char datei;

	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>>maxPrim;
	cout<<"\nMoechten Sie die Resultate in C:Primzahlen.txt schreiben? (j oder n): ";
	cin>>datei;
	cout<<"\nErmittlung laeuft...";

	while (i <= maxPrim - 1) { //Damit nur bis zu maxPrim berechnet wird
		y = x / k; //Zahl wird durch eine gerade Zahl geteilt | k beginnt bei 1 und soll maximal so groß wie x, also die zahl die auf eine Primzahl überprüft wird, werden
		if (y == (int) y) { //Ergebnis wird auf Ganzzahligkeit geprüft
			if (y != 1) {
				if (y == x) { //Wenn Ergebnis gleich Ausgangszahl und nicht 1 ist (bei k = 1 der fall), dann wird k erhöht
					k = k + 1;
				}

				else { //Wenn Ergebnis nicht 1 und nicht Ausgangszahl, dann kann es keine Primzahl mehr sein und die nächsthöhere Zahl wird getestet
					x = x + 1; 
					k = 1;
				}
			}

			else if (y == 1) { //Wenn Ergebnis 1 ist (nur der Fall wenn x durch k mit k = x geteilt wird), dann ist es eine Primzahl, da ansonsten vorher x schon erhöht worden wäre
				Prim [i] = x;
				i = i + 1;
				k = 1;
				x = x + 1;
			}
		}

		else { //Wenn Ergebnis nicht ganzzahlig, wird k erhöht
			k = k + 1;
		}
	}

	cout<<endl;

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

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

	return 0;
}

Wieso sollte ich jetzt eine Endlosschleife machen und dann mit break unterbrechen? Das würde das Programm doch nur verlängern, wenn es doch auch so funktioniert?

EDIT: Das mit dem Primzahlen in eine Datei schreiben klappt, wie man sieht, noch nicht. Ich arbeite da noch dran. Weil wenn man alle Primzahlen bis 100.000 berechnet, können die ja nicht alle in einem Fenster angezeigt werden.

EDIT 2: Ich habe jetzt noch folgendes ans Ende der Schleife geschrieben und die benötigten Variablen auch definiert.

if (x / maxPrim >= 0.25 && A == 0) {
			cout<<"\n25% fertig!"<<endl;
			A = 1;
		}
		if (x / maxPrim >= 0.5 && B == 0) {
			cout<<"50% fertig!"<<endl;
			B = 1;
		}
		if (x / maxPrim >= 0.75 && C == 0) {
			cout<<"75% fertig!"<<endl;
			C = 1;
		}
		if (x / maxPrim == 1 && D == 0) {
			cout<<"Ermittlung abgeschlossen!\nWerteausgabe folgt!"<<endl;
			D = 1;
		}

Nun ist mir aufgefallen, dass das Ermitteln der Primzahlen selbst bei 100.000 innerhalb von 13 Sekunden vorbei ist.
Aber wieso dauert es ab dem Zeitpunkt noch so ewig lange (habs nicht gemessen, da die Werte nach 2 Minuten immer noch nicht ausgegeben wurden)bis das Programm anfängt die Werte auszugeben? Also ab dem Zeitpunkt sind ja alle Werte berechnet und eigentlich muss er ja nur noch die Variablen ausgeben. Wieso dauert das so lange, bis der erstmal damit anfängt die auszugeben?

EDIT3: Problem hat sich erledigt, hatte nen Denkfehler drinne

[knivil]

Du hast ja immer noch floats drin.

[jkhsjdhjs]

knivil schrieb:

Du hast ja immer noch floats drin.

Wie meinst du das? Ich muss y, x & k durch float definieren, da es sonst nich klappt. Und wieso sollte ich das nicht drin haben?

[SG1]

jkhsjdhjs schrieb:

knivil schrieb:

Du hast ja immer noch floats drin.

Wie meinst du das? Ich muss y, x & k durch float definieren, da es sonst nich klappt.

Nein.

Und wieso sollte ich das nicht drin haben?

Weil floats bei 'nem zahlentheoretischen Problem nichts zu suchen haben. Rundungsfehler (wie sie bei float automatisch irgendwann entstehen) sind da katastrophal.

[jkhsjdhjs]

Soll ich da dann double oder long double verwenden oder was empfehlt ihr?

[Sone]

jkhsjdhjs schrieb:

Soll ich da dann double oder long double verwenden oder was empfehlt ihr?

Überhaupt keine Fließkommazahlen. Denn du brauchst keine.

Daher auch die Devise: Immer sagen was du erreichen willst, nicht womit. Und wo sinnvoll auch das höher gestellte Problem.

[Bashar]

Der richtige Tipp wurde doch schon längst gegeben (von µ), nur der OP hat ihn ignoriert.

[jkhsjdhjs]

Ich muss doch x durch k teilen und in y speichern. Ich muss dann bei y überprüfen, ob es int ist oder nicht. Und wenn x oder k schon int sind, kommt für y immer int raus, auch wenn nur y float ist. Deshalb muss ich die drei Variablen per float definieren. Da x und k sowieso immer nur ganzzahlig sind, macht das denke ich nichts. Und y wird immer neu berechnet.

Achso, das mit Modulo. Ok, da müsste ich mich noch reinlesen, weiß nicht was das ist.

[otze]

Modulo ist division mit Rest.

1 % 3 = 1
2 % 3 = 2
3 % 3 = 0
4 % 3 = 1

Eine Zahl ist genau dann durch eine andere teilbar, wenn die division rest 0 hat und die Zahl selbst nicht 0 ist.

[Kellerautomat]

Du willst also, dass dein Programm eine nutzerdefinierte Anzahl an Primzahlen findet. Zuerst brauchen wir also eine Funktion, die feststellt, ob eine Zahl eine Primzahl ist. Die Idee ist dabei folgende: Wir pruefen, ob unsere Zahl durch 2, 3, 4, ..., wurzel(Zahl) teilbar ist. Ist die Zahl durch keine dieser Zahlen teilbar, dann haben wir eine Primzahl gefunden. *

Wie prueft man nun, ob eine Zahl durch eine andere teilbar ist? Das geht mit dem Modulo-Operator, den µ und Otze bereits angesprochen haben. Der gibt naemlich den Rest einer Division zurueck. Und wenn der Rest der Division 0 ist, ist eine Zahl durch die andere teilbar.

Wir bekommen also:

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
}

Jetzt brauchen wir noch den Teil, der den User fragt, wie viele Primzahlen er haben moechte und diese dann ausrechnet.

int main()
{
	std::cout << "Wie viele Primzahlen?\n";

	unsigned numberOfPrimes;
	std::cin >> numberOfPrimes;

	// 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 ...
		{
			std::cout << n << ' '; // ... dann gib die zahl aus ...
			++count; // ... und erhoehe die anzahl gefundener primzahlen um 1
		}
}

Jetzt setzen wir das ganze noch zusammen und bekommen:

#include <iostream>

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 main()
{
	std::cout << "Wie viele Primzahlen?\n";

	unsigned numberOfPrimes;
	std::cin >> numberOfPrimes;

	// 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 ...
		{
			std::cout << n << ' '; // ... dann gib die zahl aus ...
			++count; // ... und erhoehe die anzahl gefundener primzahlen um 1
		}
}

http://ideone.com/I5qoPv

Wenn es Unklarheiten gibt, einfach nachfragen.

* Ist natuerlich doof, alle Zahlen durchzugehen. Wem es besser gefaellt, der kann Vielfache von 2 und 3 gleich ueberspringen:

bool isPrime(unsigned n)
{
	if(n == 2 || n == 3)
		return true;

	if(n < 2 || n % 2 == 0 || n % 3 == 0)
		return false;

	for(unsigned i = 5, delta = 2; i * i <= n; i += delta, delta = 6 - delta)
		if(n % i == 0)
			return false;

	return true;
}

[kamelkacke]

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

Greets

[jkhsjdhjs]

@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?

[Th69]

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.

[jkhsjdhjs]

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?

[Nathan]

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?

[jkhsjdhjs]

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.