Primzahlen ermitteln

[Gast]

Sorry, keine Lust mich in dieses unleserliche Gewirr mit y,i,k und x reinzudenken.

Nur soviel: x / k ist eine integer-division, das ergebnis ist ganzzahlig.
Verwende Modulo um auf Teilbarkeit ohne Rest zu prüfen.

Ehrlich gesagt: Wirf den Ansatz weg und fange komplett neu an.

[jkhsjdhjs]

Ok, ich werde es zuerst mal probieren, indem ich x und k auch furch float definiere. Mal sehn, obs dann klappt. Danke

EDIT: GENIAL!
Hat, direkt funktioniert, klappt einwandfrei

Danke Danke Danke

Und hab

int Prim [19]

auf

int Prim [20]

geändert, wegen dem Fehler mit Stacking around variable ... was corrupted

[Gast]

Nein hör auf mit dem Quatsch. Das ist ein Zahlentheoretisches Problem und da haben Fließkommawerte nichts zu suchen. Nochmal: Modulo-Operator!

Edit: OMG was hab ich angerichtet ....

[SeppJ]

µ schrieb:

Ehrlich gesagt: Wirf den Ansatz weg und fange komplett neu an.

Die übliche Lösung für solch doofen Aufgaben wäre:

cout << "   2      3      5      7     11     13     17     19     23     29" 
        "  31     37     41     43     47     53     59     61     67     71\n";

Bloß um zu zeigen, dass die Aufgabe schlecht gestellt ist.

(Und dann macht man es aber noch einmal richtig, in dem Sinne, wie die Aufgabe eigentlich gestellt sein sollte.)

[Gast]

SeppJ schrieb:

Bloß um zu zeigen, dass die Aufgabe schlecht gestellt ist.

Damit zeigen wirs dem Lehrer aber!!!111

[Sone]

@SeppJ:

ich soll für die Schule ein Programm schreiben. welches die ersten 20 Primzahlen ermittelt

Das suggeriert bereits, dass das Programm nicht weiß, welche Primzahlen es gibt.

[Marthog]

Also ersteinmal musst du das Problem ordentlich aufbauen. Dazu hast du eine Funktion, die Ein- und Ausgabe entgegennimmt, eine Funktion, die die Hauptschleife enthält, ein eine, die überprüft, ob x eine Primzahl ist.
Außerdem solltest du dir mal For-schleifen anschauen und nicht solche komischen while-if-Konstruktionen aufbauen.

Sone schrieb:

@SeppJ:

ich soll für die Schule ein Programm schreiben. welches die ersten 20 Primzahlen ermittelt

Das suggeriert bereits, dass das Programm nicht weiß, welche Primzahlen es gibt.

Es ist doch egal, ob man das selber macht oder den Compileroptimierer machen lässt. Richtig gestellte Aufgabe wäre es, die ersten n Primzahlen zu finden, dann kann man nicht einfach per lookup-table arbeiten.

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