Sieb des Eratosthenes

pureGewalt

Mitglied
Guten Tag zusammen,

ich habe ein Problem beim verstehen einer Aufgabenstellung:
Implementieren Sie die als „Sieb des Eratosthenes“ bekannte Primzahlberechnung mit Hilfe eines Arrays. Das Array repräsentiert alle ganzen Zahlen bis zu einer maximalen Zahl n (die von der Console eingelesen wird!). Nun werden nacheinander alle Vielfachen aller Zahlen, die kleiner als n/2 sind, im Array markiert. Diejenigen Zahlen im Array, die danach noch keine Mar-kierung tragen, sind die Primzahlen.

Ebenfalls zu beachten ist das ich keine Multiplikation oder Division im Quellcode haben darf. Und ich verstehe nicht ganz weil in der aufgabenstellung was steht von "n/2" ?

Auf jeden Fall fehlt mir hier total der Ansatz bin noch komplett neu auf dem Gebiet und das mit den Arrays finde ich noch sehr schwer. Ich möchte hier keineswegs um die Lösung bitten, aber ich bräuchte unterstützung beim verstehen wie ich das ganze angehe.. :/

Das einlesen von n wäre jetzt kein Problem aber das mit den Arrays hm.

hoffe das passt hier rein.

Liebe Grüße !!
 
K

kneitzel

Gast
Also für das Verständnis vom Sieb des Eratosthenes würde ich https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes empfehlen.

Aber in Kurzform: Wenn eine Zahl keine Primzahl ist, dann gibt es einen Teiler, der kleiner als die Primzahl ist.

Wenn Du nun in einem Zahlenstrahl alle Zahlen durchgehst (ab der 2) und dann alle vielfachen immer rausstreichst, dann ist sicher gestellt, dass die nächste Zahl, die nicht heraus gestrichen ist, eine Primzahl ist.

Ist ja auch logisch, denn wäre es keine Primzahl, dann müsste es eine Zahl kleiner geben, durch die diese Zahl teilbar ist. Oder mit anderen Worten: Die Zahl wäre ein Vielfaches der kleineren Zahl. Aber per Definition wäre dann ja die vermeintliche Primzahl als Vielfaches der kleineren Zahl herausgestrichen worden!

Beispiel für 1-10, wir fangen bei der 2 an und streichen alle Vielfachen von 2:
1, 2, 3, 5, 7, 9 (4, 6, 8 sind gestrichen)
Nun ist die Aussage, dass die 3 eine Primzahl ist. Ok. Und nun streichen wir die Vielfachen von 3:
1, 2, 3, 5, 7 (9 ist nun auch gestrichen)
Nun ist die nächste Zahl die 5, diese ist auch eine Primzahl, alle vielfachen Streichen und dann bleibt es bei
1, 2, 3, 5, 7 ... und 7 ist auch eine Primzahl.

War das soweit verständlich?
 

mihe7

Top Contributor
Und ich verstehe nicht ganz weil in der aufgabenstellung was steht von "n/2" ?
Stimmt, es reichen die Vielfachen aller Zahlen bis zur Wurzel aus n.

Das einlesen von n wäre jetzt kein Problem aber das mit den Arrays hm.
Ein Array ist ganz simpel: Du hast eine feste Anzahl von Elementen gleichen Typs, die alle mit dem selben Namen über einen Index angesprochen werden.

Sagen wir mal, Du möchtest ein Array für int-Elemente haben und dieses Array soll 50 Elemente aufnehmen können:
Java:
int[] elemente; // deklariert "elemente" als ein Array für Elemente vom Typ int.
elemente = new int[50]; // initialisiert das Array für 50 Elemente (= reserviert Speicher für 50 Elemente)

// kurz:
int[] elemente = new int[50];
Jetzt kannst Du jedes der 50 Elemente über den Namen "elemente" und einen Index ansprechen. Der Index des ersten Elements ist 0. Du kannst Dir das wie ein Tupel in Mathe vorstellen: (a_0, a_1, ..., a_49). Das dritte Elemente erhältst Du z. B. mit elemente[2].
 
K

kneitzel

Gast
Also die Grenze ist eigentlich nicht n/2 sondern Wurzel aus n.

Also bei n = 20 reicht es, bis einschließlich 4 zu gehen. Dass man die 5 nicht mehr prüfen muss, wird direkt deutlich:
5 ist zwar ein Teiler, aber 20 / 5 = 2*2, d.h. bei der 2 wurde die 20 bereits weggestrichen!
 

pureGewalt

Mitglied
Also für das Verständnis vom Sieb des Eratosthenes würde ich https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes empfehlen.

Aber in Kurzform: Wenn eine Zahl keine Primzahl ist, dann gibt es einen Teiler, der kleiner als die Primzahl ist.

Wenn Du nun in einem Zahlenstrahl alle Zahlen durchgehst (ab der 2) und dann alle vielfachen immer rausstreichst, dann ist sicher gestellt, dass die nächste Zahl, die nicht heraus gestrichen ist, eine Primzahl ist.

Ist ja auch logisch, denn wäre es keine Primzahl, dann müsste es eine Zahl kleiner geben, durch die diese Zahl teilbar ist. Oder mit anderen Worten: Die Zahl wäre ein Vielfaches der kleineren Zahl. Aber per Definition wäre dann ja die vermeintliche Primzahl als Vielfaches der kleineren Zahl herausgestrichen worden!

Beispiel für 1-10, wir fangen bei der 2 an und streichen alle Vielfachen von 2:
1, 2, 3, 5, 7, 9 (4, 6, 8 sind gestrichen)
Nun ist die Aussage, dass die 3 eine Primzahl ist. Ok. Und nun streichen wir die Vielfachen von 3:
1, 2, 3, 5, 7 (9 ist nun auch gestrichen)
Nun ist die nächste Zahl die 5, diese ist auch eine Primzahl, alle vielfachen Streichen und dann bleibt es bei
1, 2, 3, 5, 7 ... und 7 ist auch eine Primzahl.

War das soweit verständlich?

Danke für deine Antwort das macht es für mich auf jeden Fall verständlicher.

Stimmt, es reichen die Vielfachen aller Zahlen bis zur Wurzel aus n.


Ein Array ist ganz simpel: Du hast eine feste Anzahl von Elementen gleichen Typs, die alle mit dem selben Namen über einen Index angesprochen werden.

Sagen wir mal, Du möchtest ein Array für int-Elemente haben und dieses Array soll 50 Elemente aufnehmen können:
Java:
int[] elemente; // deklariert "elemente" als ein Array für Elemente vom Typ int.
elemente = new int[50]; // initialisiert das Array für 50 Elemente (= reserviert Speicher für 50 Elemente)

// kurz:
int[] elemente = new int[50];
Jetzt kannst Du jedes der 50 Elemente über den Namen "elemente" und einen Index ansprechen. Der Index des ersten Elements ist 0. Du kannst Dir das wie ein Tupel in Mathe vorstellen: (a_0, a_1, ..., a_49). Das dritte Elemente erhältst Du z. B. mit elemente[2].

Okay gut, also kann ich damit eine gewissen Anzahl an Elementen mit dem Index dann ansprechen. Auf den Sieb bezogen könnte ich dann eventuell:

for(int zaehler = 2; zaehler <= n; zaehler ++) //Damit fällt ja dann die 1 immer weg?
int zahlenAnzahl = new int [zaehler]


könnte ich so dann auf eine Zahl beispielsweise die 2 zugreifen? und müsste jetzt eine Bedingung machen ob er diese Streichen soll? Oder nicht? Alles innerhalb der "for schleife" und somit dann sagen das es eine Primzahl ist? Das verstehe ich nicht ganz richtig, wie ich das machen soll. Vor allem ohne Division und Multiplikation.
 

mihe7

Top Contributor
könnte ich so dann auf eine Zahl beispielsweise die 2 zugreifen?
Nein. Erstens ist die Syntax ist falsch (vergleiche nochmal mit dem, was ich oben geschrieben habe), zweitens würdest Du mit "new" in der Schleife jedesmal ein Array mit zaehler Elementen erstellen. Drittens brauchst Du auf die 2 nicht zuzugreifen, die hast Du ja schon mit zaehler gegeben.

Mal ein Beispiel:
Java:
int summe;
int[] elemente = new int[50];
for (int i = 0; i < 50; i++) {
    elemente[i] = i+1;
}
summe = elemente[0] + elemente[49];
Damit würdest Du ein Array elemente erstellen, das 50 int-Elemente aufnehmen kann. In der for-Schleife würdest Du die Elemente des Arrays setzen. Ergebnis wäre
Code:
elemente[0] == 1
elemente[1] == 2
elemente[2] == 3
...
elemente[49] = 50
In der letzten Zeile wird der Wert des Arrays elemente genommen, der an Index 0 steht und mit dem Wert des Arrays elemente, der an Index 49 steht addiert. Das wäre hier also die 1 und die 50. Das Ergebnis wird in der Variablen summe gespeichert, d. h. am Ende gilt summe == 51.

Die Frage wäre erst einmal, ob Du überhaupt ein int-Array brauchst oder ob ein anderer Datentyp ggf. geeigneter wäre... welcher könnte das sein?
 

pureGewalt

Mitglied
Nein. Erstens ist die Syntax ist falsch (vergleiche nochmal mit dem, was ich oben geschrieben habe), zweitens würdest Du mit "new" in der Schleife jedesmal ein Array mit zaehler Elementen erstellen. Drittens brauchst Du auf die 2 nicht zuzugreifen, die hast Du ja schon mit zaehler gegeben.

Mal ein Beispiel:
Java:
int summe;
int[] elemente = new int[50];
for (int i = 0; i < 50; i++) {
    elemente[i] = i+1;
}
summe = elemente[0] + elemente[49];
Damit würdest Du ein Array elemente erstellen, das 50 int-Elemente aufnehmen kann. In der for-Schleife würdest Du die Elemente des Arrays setzen. Ergebnis wäre
Code:
elemente[0] == 1
elemente[1] == 2
elemente[2] == 3
...
elemente[49] = 50
In der letzten Zeile wird der Wert des Arrays elemente genommen, der an Index 0 steht und mit dem Wert des Arrays elemente, der an Index 49 steht addiert. Das wäre hier also die 1 und die 50. Das Ergebnis wird in der Variablen summe gespeichert, d. h. am Ende gilt summe == 51.

Die Frage wäre erst einmal, ob Du überhaupt ein int-Array brauchst oder ob ein anderer Datentyp ggf. geeigneter wäre... welcher könnte das sein?

Ok das müsste ich jetzt verstanden haben, habe mich jetzt nochmal damit beschäftigt, erst dachte ich, ich müsste den Datentyp double nehmen, wegen dem geteilt durch 2 oder der Wurzel, doch habe ich auch noch den Datentyp boolean mir überlegt.
Mein Ansatz:

//Variablen Deklaration
int max = 0;


//Array dekarieren
boolean[] makiere = new boolean [max];

//Makierungen auf False setzen
for(int elementZaehler = 2; elementZaehler < makiere.length; elementZaehler++) {
makiere[elementZaehler] = false;
}

Jetzt müsste ich eigentlich um diesen boolean datentyp richitg zu machen noch etwas mit true setzen.
Mein nächster Ansatz jetzt vielleicht nochmal eine for schleife für "true"?
 

mihe7

Top Contributor
Der Datentyp passt schon mal :) Auf false brauchst Du die Elemente des Arrays nach der Initialisierung nicht extra setzen: die werden standardmäßig mit false initialisiert. Schadet aber auch nicht.

Jetzt müsste ich eigentlich um diesen boolean datentyp richitg zu machen noch etwas mit true setzen.
Richtig. Überleg Dir erstmal - ohne Code - wie der Sieb im Detail funktioniert. In dem Zusammenhang auch: was soll es bedeuten, wenn eine Zahl "markiert" wurde? Du musst auch nicht sofort Java-Code schreiben, sondern kannst den Algorithmus erstmal anders formulieren.
 
X

Xyz1

Gast
Irgendwo schwirrt im Internet bestimmt eine Definition vom SdE rum.... Falls nicht, hier auch nochmal meine, Du brauchst mindestens 3 Schleifen (furchtbar viel Platz benötigt und furchtbar ineffizient... Eratosthenes hatte keine gute Idee gehabt...):
Java:
public class ET {
	public static void main(String[] args) {
		boolean[] sieb = new boolean[10_000];
		for(int i=0;i<sieb.length;i=i+2) {
			sieb[i]=true;
		}
		for(int i=3;i<sieb.length;i=i+2) {
			if(sieb[i]==false) {
				for(int j=i<<1;j<sieb.length;j=j+i) {
					sieb[j]=true;
				}
			}
		}
		for(int i=0;i<sieb.length;i=i+1) {
			if(sieb[i]==false) {
				System.out.print(i + ", ");
			}
		}
	}
}
 

Ähnliche Java Themen

Neue Themen


Oben