primzahlensieb

NC10 · 7. Dez 2009

Hallo,

ich steht irgendwie grad auf dem Schlauch: ich weis einfach nicht weiter!
Meine Aufgabe wäre mit dem Algorithmus Sieb des Eratosthenes eine Primzahlen- methode zu schreiben: public static boolean[] primzahlensieb (int m), m ist die oberste Grenze der zahlen.
Also ich habe ein Array aus Zahlen, 0 und 1 schließe ich aus, weil beides keine Primzahlen bin und setze sie deswegen auf false, den rest des Arrays muss ich auf true setzen. Soweit richtig? Das mach ich mit meiner for- Schleife. Aber dann weis ich einfach nicht weiter: ich fange dann mit 2 an also array an der Stelle 2 (hier 2 mit 0) und müsste dann alle Vielfachen von 2 aus dem array raussschmeisen. Ich weis momentan einfach nicht wie ich vorgehen soll: Kann mir jemand einen Tipp oder so?
Was ich bis jetzt habe:

Java:

public class Primzahlen {

  public static boolean[] sieb (int m)
  boolean[] zahlen = new boolean[m]; // Anlegen eines Arrays mit den Zahlen von o bis m 

  //Initialisierung dieses Arrays (alle Werte auf true setzen, ausser Elemente an der Stelle 0 und 1)
  int i;
  for (i=0, i<m+1, i++) { //durchlaufen des Arrays, jedes Element mit true belegen 
    zahlen[0]=false; //die beiden Ausnahmen auf false setzen
    zahlen[1]=false;
    zahlen[i]=true;

Was sagt ihr zu meinem Ansatz bis jetzt? Das müsste soweit ja nicht ganz schlecht sein oder? Ich weis einfach nicht weiter. Vielleicht so:

Java:

       for (i=2, i<m+1, i++) { //eine weitere for- Schleife (innerhalb der ersten), die bei i=2 beginnt
         zahlen[alle Zahlen die ein Vielfaches von i=2 sind]=false; 
         //hier weis ich nicht weiter! Wie soll ich das in korrektes Java implementieren?          Bitte bitte helfen! Dankeschön!

Ich glaube es ist gar nicht nötig die zweite for Schleife innerhalb der ersten for- Schleife zu haben.

Gruss NC!!!

nrg · 7. Dez 2009

Java:

			for(int i=3; i<zahlen.length; i++){
				zahlen[i] = true;
				for(int i2=2; i2<i; i2++){
					if ((i%i2) == 0){
						zahlen[i] = false;
					}
				}
			}

so wär ich das jetzt angegangen.

du setzt erst jeden index vom array auf true und verschachtelst zwei schleifen. In der zweiten schleife wendest zu den modulo operator auf die zwei zähler an und falls iwann mal der Rest 0 sein sollte (dh die zahl ist teilbar), setzt du den index wieder auf false. so haste alle primzahlen auf true gesetzt in einem array, dass durch den parameter m bestimmt wurde,

hoffe das hilft dir weiter.

EDIT: falls nicht ohnehin schon bekannt: hier wird der Modulo-Operator schön erklärt. wenn du den richtig anwendest, ist die Aufgabe kein Problem mehr. Modulo-Operator

grüße nrg

NC10 · 7. Dez 2009

ok super danke , das bringt mich schon weiter: Was haltet ihr dann davon in etwa? Kann noch nicht ganz richtig sein:

Java:

public class Primzahlen {
 
  public static boolean[] sieb (int m);
  boolean[] zahlen = new boolean[m]; // Anlegen eines Arrays mit den Zahlen von 0 bis m 
 
  zahlen[0]=false; //die beiden Ausnahmen auf false setzen
  zahlen[1]=false;
  zahlen[2]=true; //erste Primzahl

  for(int i=3; i<m; i++){
    zahlen[i] = true;
    for(int j=2; j<i; j++){
      if ((i%j) == 0){
        zahlen[i] = false;
      }
    }
  }
}

Ich glaube das kann so nicht ganz richtig sein: Mein Array habe ich am Anfang den Datentyp boolean zugewiesen, das heißt in meinem Array befinden sich nur eine Folge von mehreren true und false. Seh ich das richtig?

nrg · 7. Dez 2009

NC10 hat gesagt.:
Java:

zahlen[0]=false; //die beiden Ausnahmen auf false setzen zahlen[1]=false;

überflüssig

NC10 hat gesagt.:
Ich glaube das kann so nicht ganz richtig sein: Mein Array habe ich am Anfang den Datentyp boolean zugewiesen, das heißt in meinem Array befinden sich nur eine Folge von mehreren true und false. Seh ich das richtig?

jo, das siehst du richtig. hab mich schon gefragt, was du damit vorhast... also prinzipiell macht es das, was du willst. hab es mal getestet mit m=1000 und ne Ausgabe dazu gemacht. Primzahlen stimmen.

Java:

			for(int i=0;i<zahlen.length;i++){
				if(zahlen[i])
					System.out.println(i);
			}

aber ich glaub eher, dein Array soll Integer sein und du schreibst die Primzahlen direkt in das Array.

grüße nrg

NC10 · 8. Dez 2009

So ich hab jetzt mein Programm folgendermaßen:

Java:

public class Primzahlen {

  public static boolean[] siebDesEratosthenes(int n) {
    boolean[] array = new boolean[n]; 

    for(int i=3; i<n; i++){ 
      array[i] = true;
        for(int j=2; j<i; j++){
          if ((i%j) == 0){
            array[i] = false;
          }
        }
    }
    for (int k=0; k<n; k++) {
      if(array[k]==true){
        return k;
      } 
    }
  }
  public static void main(String[] args) {
    System.out.println(siebDesEratosthenes(1001));
  }
}

Ich bekomme folgende Fehlermeldung:
Primzahlen.java:16: incompatible types
found : int
required: boolean[]
return k;
^
1 error

Und ich verstehs einfach nicht: Ich greif doch über mein int k als Index auf mein Array mit boolean Werten zu und gib den int wert zurück. Warum wird ich boolean verlangt. Versteh ich einfach nicht ... Wer kann mir da denn helfen? Danke schon mal im Vorraus!

nrg · 8. Dez 2009

du versuchst von einer methode, die als rückgabe ein array vom typ boolean erwartet einen integer zurückzugeben. das geht nicht.... es wäre auch mal vorteilhaft, wenn du mir verraten würdest, was das programm können soll... ich verstehe nämlich bis jetzt noch nicht warum der arraydatentyp überhaupt ein boolean ist.....

EDIT: nochmal um das klarzumachen... der return ist ein komplettes Array vom typ boolean... also das einzige, das der compiler hier akzeptieren würde, wäre:

Java:

return array;

das allerdings nicht in einer if-abfrage, weil dann der compiler nicht sicher weiß, ob dieser code überhaupt erreicht werden kann.

grüße

NC10 · 8. Dez 2009

ja okay das verstehe ich.
Das mit dem boolean array erzeugen dessen Indexzahlen den Primzahlen entsprechen, ist Vorgabe bei meiner Aufgabe. Also ich speichere natürlich in dem array werte true und false Werte! Beim index 0 muss false stehen bei einer Primzahl true. also ich geh das Array zurück mit return. das klappt auch. meine For-schleife sollte mir den Inhalt des arrays ausgeben, aber nicht die true-Werte sondern eben den Index. Wie kann ich das dann machen?

function · 8. Dez 2009

Java:

int i = 0;
for(boolean z : array) {
  if(z) {
    System.out.println(i);
  }
  i++;
}

nrg · 8. Dez 2009

nrg hat gesagt.:
Java:

for(int i=0;i<zahlen.length;i++){ if(zahlen[i]) System.out.println(i); }

stand doch bereits ein paar postings drüber. du loopst über das komplette array und wenn dein arrayfeld true ist, gibste den counter aus.

NC10 · 8. Dez 2009

naja aber genau das mach ich doch und ich bekomm immer wieder die Fehlermeldung von oben. dass ein int gefunden wurde aber ein boolean erwartet wird

Painii · 8. Dez 2009

NC10 hat gesagt.:
naja aber genau das mach ich doch und ich bekomm immer wieder die Fehlermeldung von oben. dass ein int gefunden wurde aber ein boolean erwartet wird

Du hast in der Methode return k geschrieben, nix mit System.out.println(k).

Entweder du suchst in der main-methode alle true-werte raus und gibts sie aus (dahin die for-schleife verlagern), oder du änderst return k in ein print/println und gibts am Ende aber trotzdem das Array zurück.

Aber dein return k wird immer weiter den Fehler bringen, weil ein int nunmal kein boolean[] ist

NC10 · 8. Dez 2009

ok danke: es funktioniert noch nicht ganz? hmm... weis das jemand?
So in etwa?

Java:

public class Primzahlen {

  public static boolean[] siebDesEratosthenes(int n) {
    boolean[] array = new boolean[n]; 

    for(int i=3; i<n; i++){ 
      array[i] = true;
        for(int j=2; j<i; j++){
          if ((i%j) == 0){
            array[i] = false;
          }
        }
    }
    return array;
  }
  public static void main(String[] args) {
    siebDesEratosthenes(1001);
    for (int k=0; k<n; k++) {
      if (array[k]==true) {
        System.out.println(k);
      }
    }
  }
}

array und n erkennt er nun nicht! Wie kann ich die beiden Variablen jetzt auch in meiner main Methode sichtbar machen?

function · 8. Dez 2009

in der main methode versuch es mal mit:

Java:

  public static void main(String[] args) {
    int n = 1001;
    boolean[] sieb = new boolean[n];
    sieb = siebDesEratosthenes(n);
    for (int k=0; k<n; k++) {
      if (sieb[k]) {
        System.out.println(k);
      }
    }
  }

NC10 · 8. Dez 2009

ja super, danke, jetzt erkennt er nur das array noch nicht! Muss das irgendwie als Klassenvariable definieren, so dass es im ganzen Programm sichtbar ist. Wie???
müsste doch eigetnlich mit public static boolean [] ... oder so gehen, oder?

function · 8. Dez 2009

hab nochmal kurz was geändert jetzt müßte es laufen.

nrg · 8. Dez 2009

NC10 hat gesagt.:

Java:

public class Primzahlen {

  public static boolean[] siebDesEratosthenes(int n) {
    boolean[] array = new boolean[n];    //<------  ist NUR in DIESER Methode sichtbar
    for(int i=3; i<n; i++){ 
      array[i] = true;
        for(int j=2; j<i; j++){
          if ((i%j) == 0){
            array[i] = false;
          }
        }
    }
    return array;
  }
  public static void main(String[] args) {
    siebDesEratosthenes(1001);
    for (int k=0; k<n; k++) { //<------- n kennt er hier auch NICHT!
      if (array[k]==true) {  //<-------- array kennt er hier NICHT! 
        System.out.println(k);
      }
    }
  }
}

du musst das ganze wieder in ein array zurückgeben. das kannste dann auch einfach wieder "array" nennen.... dann noch n anpassen mit

Java:

array.length

dann passt das

NC10 · 8. Dez 2009

versteh nicht ganz wie ich das wieder in einem array zurückgeben soll??? gibt es nicht eine Möglichkeit n bzw array als Klassenvariable zu definieren, auf die man dann in der Main Methode auch zugreifen kann?

nrg · 8. Dez 2009

function hat deine Hausaufgaben bereits gemacht...

copy&paste, debuggen und den code versuchen zu lesen.

function · 8. Dez 2009

du hast die methode siebDesEratosthenes so gestaltet, dass sie ein boolean array zurück gibt was auch eine gute idee ist, das solltest du dann auch in der main methode dann ausnutzen. Du musst dazu einfach in der main methode ein boolean array gleicher größe erstellen darin die rückgabe der methode "speichern".

NC10 · 8. Dez 2009

Ok super jetzt klappts, Vielen Dank schon mal. Allerdings hätt ich jetzt noch ne Fragen:

Java:

public class Primzahlen {

  public static boolean[] siebDesEratosthenes(int n) { //Methode siebDesEratosthenes vom Typ boolen mit Parameter n 
  boolean[] array = new boolean[n]; //neues Array mit der Länge n erstellen
  
    //1. for- Schleife um alle Elemente des Arrays ab Index 3 mit dem Werte true zu belegen 
    for(int i=3; i<n; i++){  //1. Schleifendurchgang: i=3, array[3]=true; j=2, 2<3, 3%2 ergibt nicht 0, also array[3]=true  
      array[i] = true;       //[B]2. Schleifendruchgang: i=4, array[4]=true; j=2, 2<4, 4%2 ergibt 0, also array[4]=false[/B]
        for(int j=2; j<i; j++){  /[B]/dann j um 1 erhöhen: j=3, 3<4, 4%3 ergibt nicht 0, also array[4] nicht 0, also array[4]=[/B]
          if ((i%j) == 0){       [B]//true???[/B] , dann j um 1 erhöhen schleife geht nicht weiter da 4 nicht kleiner 4 
            array[i] = false; //3. Schleifendurchgang: i=5, array[5]=true, j=2, 2<5, 5%2 ergibt nicht 0, also array[5]=true 
          }                   //j=3, 3<5, 5%3 ergibt nicht o , also array[3] true 
        }                     //j=4 4<5, 5%4 ergibt nicht o also array[5] true 
    }                         //4. Schleifendurchgang: i=6, array[6]=true, int j=2, 2<6, 6%2 ergibt 0, also array[6]=false
    return array;             //dann j um 1 erhöhen: j=3, 6%3 ergibt 0, also array arry[6]=false, ......
  }
  public static void main(String[] args) {
    boolean[] array=siebDesEratosthenes(1001);
    System.out.println("Alle Primzahlen zwischen 0 und 1000:");
    for (int k=0; k<array.length; k++) {
      if (array[k]==true) {
        System.out.print("," +k);
      }
    }
  }
}

Ich hab Kommentare eingefügt und ich frage mich warum Index 4 einmal mit false und einmal mit true belegt wird, aber nicht ausgegeben wird ....

Und ich hab eine weitere Frage: Ich habe bisher Ergebnisse immer mit Hilfe einer main- Methode auf der Konsole ausgegeben. So wie hier auch. Wie könnte man jetzt zum Beispiel die Primzahlen auf dem Terminal ausgeben ohne eine main- Methode zu nutzen: Also wenn die Methode , die die Primzahlen ausgeben soll zum Beispiel so aussieht:

Java:

public static void primzahlenaufterminal(int n)

Kann man da auch System.out.println verwenden? Danke wiederum im Vorraus für die super Hilfe hier!

Java:

public static void primzahlenaufterminal(int n){
    boolean[] array=siebDesEratosthenes(n);
    for (int k=0; k<array.length; k++) {
      if (array[k]==true) {
        System.out.print("," +k);
      }
    }
  }

funktioniert nicht: javac sagt Exception in thread "main" java.lang.NoSuchMethodError: main!!!

Aber es muss doch möglich sein solche Ausgaben ohne einer main- Methode zu machen, wie?

function · 8. Dez 2009

weil bei der überprüfung kein else gesetzt wird, also selbst wenn ein rest bleibt wird der wert nicht wieder auf true gesetzt, sondern einmal false immer false, dass ist auch der grund warum dieser algorithmus überhaupt funktioniert.

NC10 · 8. Dez 2009

ahja logisch klar. Danke schon mal! jetzt bleibt nur noch die sache mit der main-Methode. ich hoffe des kann mir hier auch noch jemand erklören....

Ein Keks · 8. Dez 2009

natürlich kannst du den code in ne andre methode auslagern. allerdings braucht ein programm immer eine main methode (einzige ausnahme sind Applets) die ist halt nunmal der einstiegs punkt für dieses. du kannst natürlich in der main deine primzahlenaufterminal-methode aufrufen aber du kannst die main nicht weglassen

nrg · 9. Dez 2009

NC10 hat gesagt.:
Und ich hab eine weitere Frage: Ich habe bisher Ergebnisse immer mit Hilfe einer main- Methode auf der Konsole ausgegeben. So wie hier auch. Wie könnte man jetzt zum Beispiel die Primzahlen auf dem Terminal ausgeben ohne eine main- Methode zu nutzen: Also wenn die Methode , die die Primzahlen ausgeben soll zum Beispiel so aussieht:

Java:

public static void primzahlenaufterminal(int n)

Kann man da auch System.out.println verwenden? Danke wiederum im Vorraus für die super Hilfe hier!

Java:

public static void primzahlenaufterminal(int n){ boolean[] array=siebDesEratosthenes(n); for (int k=0; k<array.length; k++) { if (array[k]==true) { System.out.print("," +k); } } }

funktioniert nicht: javac sagt Exception in thread "main" java.lang.NoSuchMethodError: main!!!

Aber es muss doch möglich sein solche Ausgaben ohne einer main- Methode zu machen, wie?

also wie schon mein vorposter gesagt hat, brauchen java applications immer eine main() methode... natürlich könntest du auch den kompletten code + ausgabe in die nethode auslagern. dann brauchst du keinen rückgabe-wert mehr und rufst in der main() nurnoch die methode mit dem parameter auf und fertig. das bleibt alles in deinem eigenen ermessen, für was du den code auslagerst. ein hintergedanke bei der ganzen sache ist natürlich die codewiederverwertbarkeit. wenn du dir vorstellen kannst, dass du öfters primzahlen bis zu einem Wert x ermitteln und sie dann immer auf konsole ausgeben möchtest, macht es durchaus sinn, die ausgabe auch in die methode auszulagern...

NC10 · 9. Dez 2009

Vielen dank für euere Hilfe! Ich brauche also eine main-Methode: Dann hätt ich noch eine letzte Frage:
- In meiner Aufgabe steht wort wörtlich:
a) Verfasse eine Klasse Primzahlen mit einer Methode siebDesErathothenes (das hätten wir bereits erledigt)
b) Schreiben sie in die Klasse Primzahlen zusätzlich eine Methode public static void primzahlenaufterminal(int n), die die Primzahlen auf dem Terminal ausgibt
Wie würdet ihr dann Aufgabe b machen?
c) main-Methode schreiben, die die Methode aus b) mit einen int wert als Parameter aufruft

Glaubt ihr dass man nachdem man Aufgabe b gemacht hat, die Zahlen wirklich schon auf den Terminal sehen soll, oder dass das AUsgeben auf dem Terminal ledeglich die Aufgabe sein soll. letzendlich ausgeben macht dann Aufgabe b, oder? weil ohne main- Methode gehts ja nicht?

nrg · 9. Dez 2009

Java:

public class Primzahlen {
	  public static void main(String[] args)
	  {
		  primzahlenaufterminal(1001);
	  }
	  public static void primzahlenaufterminal(int n)
	  {
		    boolean[] array = new boolean[n];
		    array = siebDesEratosthenes(n);
		    for (int i=0; i<array.length; i++)
		    {
		      if (array[i])
		        System.out.println(i);
		    }
	  }
	  public static boolean[] siebDesEratosthenes(int n) 
	  {
		    boolean[] array = new boolean[n];
		    array[2] = true;
		    for(int i=3; i<array.length; i++)
		    { 
		      array[i] = true;
		        for(int j=2; j<i; j++)
		        {
		          if ((i%j) == 0)
		            array[i] = false;
		        }
		    }
		    return array;
	  }
}

wurde eigentlich schon alles gesagt.

grüße
nrg

EDIT: falls du eine entwicklungsumgebung wie eclipse benutzt: setz dich hin und debugg das Programm ein paar mal, damit du verstehst, was da passiert. Deine Fragen in dem Thread sprechen für sich, dass du das noch nicht ganz verstanden hast...

NC10 · 9. Dez 2009

Vielen vielen Dank! Ja einiges hab ich noch nicht verstanden, aber es wird! Danke vielen Dank!

blubdieblubblub · 9. Dez 2009

ich habe die gleiche aufgabe und hab versucht das mit den vielfachen anders zu lösen:
wenn eine index-zahl true ist, dann wird solange n*index<Menge.lenght gilt an der position n*index ein false eingetragen

dummerweise kriege ich zwar die primzahlen, aber auch einige andere angezeigt, die es eigentlich garnicht sein dürften, z.B. 25

wo ist mein fehler???

Java:

{

	public static boolean[] siebDesErastothenes(int n)
	{	
	boolean[] Menge = new boolean[n];
	int i;
	for (i = 2; i < n; i++)  //alle zahlen ab 2 werden auf true gesetzt
		{
		Menge[i] = true;
		}
	for (i = 2; Menge[i] == true; i++)  // alle zahlen ab 2 werden durchsucht, ob sie "true" als wert haben
		{
		for (int faktor = 2; faktor*i < n; faktor++)  //wenn eine Zahl true ist, dann werden alle vielfachen auf false gesetzt (solange faktor*i < n ist - ich kann ja in einem array der länge 20 die 25 nicht false setzen...)
		Menge[i*faktor] = false;
		}
	return Menge;
	
	}

nrg · 9. Dez 2009

sehr interessant gelöst

blubdieblubblub hat gesagt.:
Java:

for (i = 2; Menge[i] == true; i++) // alle zahlen ab 2 werden durchsucht, ob sie "true" als

hier ist der fehler würde ich sagen. beim ersten loop von der inneren schleife setzt du bereits 4 auf false. dh er kommt garnet so weit die vielfachen von 5 auf false zu setzen.

grüße

edit: wirst glaube nicht drumrum kommen den solange wie i<n ist loopen zu lassen.

blubdieblubblub · 9. Dez 2009

ach weil der loop sobald menge nicht mehr true ist verlassen wird!?

wenn ja, dann muss ich mir nen anderen weg überlegen wie ich des mit den schleifen machen...

blubdieblubblub · 9. Dez 2009

sehr geil!
jetz hab ichs mit i<n gemacht und innen einfach noch ein "if"
und jetz gehts

danke!

nrg · 9. Dez 2009

genau. und das erste mal ist er false bei menge[4], weil du ja vorher bei 2 schon alle vielfachen von 2 auf false gesetzt hat...

dh zu menge[5] wird es nie kommen.

wie schon gesagt, kannst aber auch einfach solange loopen wie i<n..

edit: grad gleichzeitig geschrieben

. gern

primzahlensieb

Mitglied

Top Contributor

Mitglied

Top Contributor

Mitglied

Top Contributor

Mitglied

Bekanntes Mitglied

Top Contributor

Mitglied

Bekanntes Mitglied

Mitglied

Bekanntes Mitglied

Mitglied

Bekanntes Mitglied

Top Contributor

Mitglied

Top Contributor

Bekanntes Mitglied

Mitglied

Bekanntes Mitglied

Mitglied

Bekanntes Mitglied

Top Contributor

Mitglied

Top Contributor

Mitglied

blubdieblubblub

Gast

Top Contributor

blubdieblubblub

Gast

blubdieblubblub

Gast

Top Contributor