Sieb des Erathostenes

[holzi]

Hi, habe ein Problem! Und zwar gibt er mir auch noch in der main die komplette Länge von prim wieder! Wie kann ich mittels meinem Quellcode es anstellen das nur maximal die Primzahlen ausgegeben werden? Muss ich dafür aus der Methode sieb 2 Werte übergeben?

public static void main(String args[])
	{	
		int n;
		System.out.println("====SiebDesErathostenes====\n");
		do{
			System.out.print("Obergrenze: ");
			n=IO1.einint();
			if(n<=0)
			System.out.println("x>0!");
		}while(n<=0);
		int[] prim=sieb(n);
		for(int i=0; i<prim.length; i++)
		{
			System.out.println(prim[i]);
		}
	}
	
	static int[] sieb(int n)
	{
		boolean[] sieb = new boolean[n+1];
		sieb[0] = false;
		sieb[1] = false;
		for (int i = 2; i <= n; i++)
			sieb[i] = true;
		int anz = 0;
		for (int i=2; i*i<=n; i++)
		{
			if (sieb[i])
			{
				for (int j=2*i; j<=n; j+=i)
				{
					sieb[j] = false;
					anz++;
				}
			}
		}
		int prim[] = new int[anz];
		anz = 0;
		for (int i=0; i<=n; i++)
		{
			if (sieb[i])
			{
				prim[anz] = i;
				anz++;
			}
		}
		
	return prim;
	}

 

[Leroy42]

if (sieb[i]) { 
  for (int j=2*i; j<=n; j+=i) { 
    sieb[j] = false; 
    anz++;
  } 
}

Du erhöhst hier anz (Anzahl der Primzahlen) jedesmal, wenn du
eine Nicht-Primzahl gefunden hast. :autsch:

Versuch's mal mit

if (sieb[i]) { 
  anz++;
  for (int j=2*i; j<=n; j+=i) { 
    sieb[j] = false; 
  } 
}

Achtung: Nicht getestet!

 

[Tobias]

Die Wiederverwendung deiner Variablen anz macht den Code übrigens nicht gerade intuitiv verständlicher.

mpG
Tobias

 

[Leroy42]

Da findet sich endlich einer, der mit seinen Resourcen
auch wirklich sparsam umgeht, und schon hast du
wieder was zu meckern.

( )

 

[Wildcard]

Da findet sich endlich einer, der mit seinen Resourcen
auch wirklich sparsam umgeht, und schon hast du
wieder was zu meckern.

Ein boolean Array ist alles andere als sparsam :bae:

 

[Gast]

wie könnte man denn jetzt aus der Methode 2 Werte zurückgeben mittels return?

 

[Tobias]

Wieso willst du denn zwei Werte aus deiner Methode zurückgeben?

Tupel sind als Sprachelemente nicht definiert in Java, wenn du sowas haben möchtest, mußt du dir eine entsprechende Klasse schreiben...

mpG
Tobias

 

[Leroy42]

Du könntest auch ein Array zurückgeben:

int[] sumProd(int a, int b) {return new int[] {a+b, a*b};}

Ist aber weder elegant noch allgemein, da der Typ
des Arrays eindeutig sein muß.

 

[SnooP]

Vor allem versteh ich nicht wieso überhaupt? ... objektvariable anzahl machen, die hochzählen wenn primzahl gefunden und ne Methode schreiben getAnzahlPrim oder weiß ich... feddich ist die Laube. Dann hat die Methode zwar nen Seiteneffekt, aber well... who cares?


achso - da eh schon alles static ist, kannste auch anz einfach als klassenvariable deklarieren und feddich is - das ist aber bestimmt auch gar nicht im Sinne des Aufgabenstellers -der will mit Sicherheit nen Objekt sehen!

 

[holzi]

if (sieb[i]) {
  anz++;
  for (int j=2*i; j<=n; j+=i) {
    sieb[j] = false;
  }
}

ne so bekomme ich eine Fehlermeldung! Was muss ich machen?

 

[Leroy42]

ne so bekomme ich eine Fehlermeldung! Was muss ich machen?

Na toll! Woher sollen wir jetzt wissen welche Fehlermeldung und in welcher Zeile? :autsch:

Edit: Und ist es ein Compile-Fehler oder ein Laufzeitfehler?

 

[holzi]

Obergrenze: 50
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4
        at test.sieb(test.java:46)
        at test.main(test.java:13)

sry


hat sich alles etwas verschoben wegen der class 46-> prim[anz] = i; 13-> int[] prim=sieb(n);

 

[Leroy42]

Als hätte ich es nicht schon geahnt. :autsch:

Woher sollen wir wissen, welches Zeile 47 in deinem Programm ist? :shock:

Aber egal: Entweder ist es

if (sieb[i]) {

oder

    sieb[j] = false;

Die Fehlermeldung bedeutet, daß du auf deinem Array mit einem
Index zugreifen willst, der außerhalb des gültigen Bereichs [0...sieb.length-1] liegt.

Wie groß ist dein Array? n? dann darfst du nur im Bereich [0...n-1] zugreifen.

 

[Leroy42]

int prim[] = new int[anz];

in

int prim[] = new int[anz+1];

ändern.

Und nachträgliches Editieren ohne darauf hinzuweisen gildet nicht! :noe:

 

[Leroy42]

Kommando zurück!

Stimmt ja gar nicht

Ich probiers mal aus...

 

[holzi]

for(int j=2;j<=n;j++)
      {
      	if(sieb[j])
      	anz++;
      }

habe jetzt einfach noch eine 2. Schleife dazu gezugefügt!

nu klappts. Danke!

 

[Leroy42]

Deine Bestimmung der Anzahl der Primzahlen ist falsch.

Füge einfach nach dem Sieben folgendes ein

for (int i = 2; i <=n ; i++) 
  if (sieb[i]) 
    anz++;

Und nimm das andere anz++ raus.

Edit: Huch! Zu spät!