Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

[Java] Sieb des Eratosthenes
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> [Java] Sieb des Eratosthenes
 
Autor Nachricht
danifunny
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 09.10.2009
Beiträge: 2

BeitragVerfasst am: 09 Okt 2009 - 08:27:19    Titel: [Java] Sieb des Eratosthenes

Moin zusammen,
habe folgenden Code zur Berechnung von Primzahlen nach dem Prinzip des Siebs von Eratosthenes:

Zitat:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class sieb {

/**
* @param args
*/
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
System.out.println("Primzahlen anzeigen von 0 bis ... ");
BufferedReader buffer = new BufferedReader(new InputStreamReader(
System.in));
final int MAX_PRIMZAHL = Integer.parseInt(buffer.readLine());
int[] primArray = new int[MAX_PRIMZAHL]; // Array mit x Elementen
// anlegen
for (int i = 0; i <= MAX_PRIMZAHL - 1; i++) {
primArray[i] = i + 1; // Array auffüllen mit Zahlen. primArray[0] =
// 1
}
primArray = aussieben(primArray, MAX_PRIMZAHL);
int schoeneDarstellung = 0;

for (int m = 0; m < primArray.length; m++) {
if (primArray[m] != 0) {

System.out.print(" " + primArray[m] + " ");
schoeneDarstellung++;
if (schoeneDarstellung % 20 == 0) {
System.out.println(" ");

}
}

}
}

public static int[] aussieben(int[] f, int x) {
f[0] = 0; // da 1 keine Primzahl
for (int j = 1; f[j] * f[j] <= x; j++) {
if (f[j] != 0) {
for (int k = j + j; k <= x - 1; k += j) {
if (f[k] % f[j] == 0) {
f[k] = 0;
}
}
}
}
return f;
}

}


Nur leider gibt mein Programm auch Zahlen wie 55, 35, 77 usw. aus (also irgendwie vielfache von Primzahlen)....
sieht jemand den Grund für dieses Problem?

mfg
danifunny
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 09 Okt 2009 - 13:07:42    Titel:

Warum ist dein Array eigentlich ein int-Array und kein boolean-Array?

Code:

for (int j = 1; f[j] * f[j] <= x; j++)

Das ist mir etwas suspekt. Wie kommt die Laufbedingung zustande?

Code:

if (f[k] % f[j] == 0)

Hier versteh ich auch nicht, was das soll.

Genereller Tip: Optik erst ändern, wenn das Programm funktioniert...
danifunny
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 09.10.2009
Beiträge: 2

BeitragVerfasst am: 09 Okt 2009 - 13:22:05    Titel:

Annihilator hat folgendes geschrieben:
Warum ist dein Array eigentlich ein int-Array und kein boolean-Array?

Ist ne Vorgabe die ich so erfüllen muss. Natürlich wäre mir ein boolean-Array um einiges lieber, aber kann man ja nichts machen Wink..


Annihilator hat folgendes geschrieben:

Code:

for (int j = 1; f[j] * f[j] <= x; j++)

Das ist mir etwas suspekt. Wie kommt die Laufbedingung zustande?

Nach irgendwelchen mathematischen Regeln (keine Ahnung welche Razz), soll es so sein, dass man nur die Werte die kleiner als die Wurzel aus der höchsten Zahl sind auswerten muss/kann.

Annihilator hat folgendes geschrieben:

Code:

if (f[k] % f[j] == 0)

Hier versteh ich auch nicht, was das soll.

also wenn f[k] ein vielfaches von f[j] ist, dann f[k] keine Primzahl Wink...
Annihilator hat folgendes geschrieben:

Genereller Tip: Optik erst ändern, wenn das Programm funktioniert...

Danke für den Tipp, werde ihn beherzigen Very Happy
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 09 Okt 2009 - 14:25:51    Titel:

Ich glaube, du haust hier zwei Methoden zur Primzahlfindung durcheinander. Es gilt folgendes: Hat eine Zahl n keinen Teiler <= wurzel(n), so handelt es sich um eine Primzahl. Das Sieb des Erastothenes geht darauf gar nicht eín. Da wird nur schrittweise nach Primzahlen geguckt und alle Vielfache dieser gestrichen. Beispielsweise so:

Code:

      // Ausgangssituation: Jede Zahl sei prim
      boolean[] prim = new boolean[1000];
      for (int index = 2; index <= prim.length-1; index++) prim[index] = true;

      // jetzt sieben
      for (int index = 2; index <= prim.length-1; index++)
      {
         // wenn index eine Primzahl ist, dann alle ihre Vielfachen streichen (außer 0 und index selbst)
         if (prim[index])
         {
            for (int i1 = index+index; i1 <= prim.length-1; i1 += index) prim[i1] = false;
         }
      }
Dune89
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 31.03.2009
Beiträge: 160

BeitragVerfasst am: 09 Okt 2009 - 17:30:55    Titel:

Kann mir die Logik jetzt grad ned anguggn weil ich in Eile bin aber nen kleinen schönheitsfehler hab ich noch Razz :

primArray = aussieben(primArray, MAX_PRIMZAHL);


Du brauchst nicht beides übergeben ^^:
MAX_PRIMZAHL = primArray.lengh;
klar Wink

Grüße
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> [Java] Sieb des Eratosthenes
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum