Das Sieb des Eratosthenes

[micha2233]

Hab folgendes Problem: Muss die folgende Aufgabe Lösen, weiß aber nicht wie die for -Schleife lauten muss mit n quadrat < m und wie er die letzten zehn Primzahlen ausgeben soll. Kann mir da einer helfen

Pseudocode für die Berechnung aller Primzahlen kleiner als m (mit m > 0):
1. Setze sieb = {2, 3, …, m–1}.
2. Für i = 2, 3, …, mit i2 < m, wiederhole:
2.1. Wenn i zu sieb gehört:
2.1.1. Entferne alle Vielfachen von i aus sieb.
3. Jetzt enthält sieb alle Primzahlen kleiner als m.

Dazu muss ich eine Klasse BerechnePrimzahlen erstellen ,
die das folgende Interface implementiert:
import java.util.*;
public interface Eratosthenes {
Set getPrimes(long m1,long m2);
//"erzeugt" die Menge aller Primzahlen >=m1 und <m2
}
In der Klasse BerechnePrimzahlen soll Ihre main()-Methode Ihre Implementierung
testen, indem Sie für vier verschiedene Kombinationen von m1 und m2 sowohl die
Anzahl der Primzahlen zwischen m1 und m2 (im obigen Sinne) als auch die (sortierte)
Liste der letzten zehn Primzahlen dieser Menge ausgeben.

Hier mein Ansatz:

public class BerechnePrimzahlen
{
  public static void main(String argv[])
  {
    // 1. Deklaration der Variablen
    int i, j;
    int[] sieb = new int[101];

    // 2. Initialisierung des Feldes, sieb[0] unbenutzt

    for (i=1; i<101; i++)
        sieb[i]=i;

    // 3. Loeschen der Vielfachen
    for (i=2; i<=10; i++)
        for (j=2*i; j<=100; j+=i)
            sieb[j]=0;

    // 4. Ausgabe der Primzahlen
    System.out.println("\nPrimzahlen :");
    for (i=2; i<=100; i++)
        if (sieb[i]>0)
            System.out.print(sieb[i] + " ");

    // 5. Beenden des Programms
    System.exit(0);
  }
}

Danke im Voraus
Micha

 

[semi]

Hab folgendes Problem: Muss die folgende Aufgabe Lösen, weiß aber nicht wie die for -Schleife lauten muss mit n quadrat < m und wie er die letzten zehn Primzahlen ausgeben soll. Kann mir da einer helfen

Das heisst, dass du nur n Schritte durchlaufen musst. Du brauchst nur die Formel nach n aufzulösen.

n^2 < m daraus folgt n > sqrt(m)

also

n = Math.sqrt(m);

Dein Code scheint auch soweit korrekt, bis auf die Hauptschleife,
wo du die Zahlen löschst. Unnötigerweise gehst du "paar" bereits
gelöschte erneut durch.

int maxi = (int)Math.sqrt(sieb.length);

for (i=2; i<=maxi; i++)
{
  if(sieb[i]==0) // bereits gelöschte Zahlen überspringen
    continue;
  for (j=2*i; j<sieb.length; j+=i) 
    sieb[j]=0;
}

 

[micha2233]

Danke semi! Ich bin ein Stückchen weitergekommen. Muss noch die anderen Sachen programmieren.

Gruß
Micha

 

[micha2233]

Hallo nochmal,

also so seht mein Programm jetzt aus:

import java.util.*;
import javax.swing.*;
public class BerechnePrimzahlen implements Eratosthenes
{
  private long m1;
  private long m2;
  private TreeSet sieb;
  
  public BerechnePrimzahlen() {
     m1=1;
     m2=1;
     sieb = new TreeSet();
  }
  
  public TreeSet getSieb() {
     return sieb;
  }

  public TreeSet getPrimes(long m1, long m2)
  {
   long j=0;
   for (long i = m1;i<=m2;i++)
   {
    sieb.add(i);
   }
   for (long i = m1;i<=m2;i++)
   {
    if (sieb.contains(i))
    {
      for (long n=i;n<=sieb.size();n++)
      {
        j=i;
        sieb.remove(j*n);
      }
    }
   }
   return sieb;
  }

  public static void main (String []args)
  {
    // Deklaration:
    long m1=1,m2=1;
    TreeSet sieb;
    String ausgabe="",temp="";

    // Eingabefeld erzeugen:
    JTextField[] feld = {new JTextField(),new JTextField()};
    Object[] msg = {"Von:", feld[0],"Bis:", feld[1]};
    // Dialogfenster anzeigen:
    (new JOptionPane(msg)).createDialog(null,"Primzahlen von bis").setVisible(true);
    // m1 parsen:
     m1=Integer.parseInt(feld[0].getText());
    // Die 1 auschlißen:
    if (m1==1)
      {
       m1++;
      }
    // m2 parsen
    m2=Integer.parseInt(feld[1].getText());
    // Primzahlen in Methode berechnen lassen:
    BerechnePrimzahlen bp = new BerechnePrimzahlen();
    sieb = bp.getPrimes(m1,m2);
    // Ausgabe erstellen:
    ausgabe += "Bereich von " + m1 + " bis " + m2;
    ausgabe += "\nAnzahl der Primzahlen: " + sieb.size();
    ausgabe += "\nDie letzten 10 Primzahlen: ";
    // Die letzen 10 Primzahlen sortieren:
    int z=0;
    int max = sieb.size();
    while ( z < 10 && z < max ) {
      temp= sieb.last()+", " + temp;
      sieb.remove(sieb.last());
      z++;
    }
    ausgabe+="\n"+temp;
    //Ausgabe:
    JOptionPane.showMessageDialog(null,ausgabe,"Primzahlen",JOptionPane.INFORMATION_MESSAGE);
    System.exit(0);
  }
}


import java.util.*;

public interface Eratosthenes
{
    Set getPrimes(long m1,long m2);
}

Aber er gibt mir alle Zahlen aus und nicht die NUR die Primzahlen. Bitte um Verbesserung meines Programms

Schöne Grüße
Micha