Sieb des Eratosthenes für Anfänger

[m4libu17]

Hi Leute,

zwecks Studium beschäftige ich mich seit 2 Monaten mit Java.
Nun ist die Aufgabe gestellt worden das Sieb des Eratosthenes zu programmieren, um damit alle Primzahlen bis zu einer einzugebenden Grenze zu finden.
Außerdem soll man noch die eingegebene Zahl in ihre Primzahlen zerlegen

An sich war das mit ein bisschen denken und rumprobieren nicht das großartige Problem das Sieb zum laufen zu bringen.

Das Problem ist nur dass das Ding effizient sein muss und ich hab echt keine Idee wie ich mein Sieb effizienter machen soll.

Ich hoffe ihr könnt mir helfen und schonmal danke im Vorraus

Hier mein Code:

public class Bsp07{
	public static void main(String[] args){
	
		int n = SavitchIn.readLineInt();             //mit der klasse SavitchIn wird eingelesen
		boolean[] liste = new boolean[n+1]; 
      boolean[] zerlegung = new boolean[n];
		int zeichenzaehler = 0;
		int a = 1, c = 1, k = 2;
		
		//liste markieren wenn nicht prim
		while(a < liste.length){
			if((a+1)%k == 0 && k < a+1){
            liste[a] = false;
            a++;
            k = 2;
         }
         else{
            if((a+1)%k == 0 && k >= a+1){
               a++;
               k = 2;
            }
            if((a+1)%k != 0 && k < a+1){
               liste[a] = true;
               k++;
            }
            
         }
		}	
		
      //ausgabe aller primzahlen, maximal 5 pro zeile
     	liste[1] = true;
      int b = 1;
		while(b < n){
			if(liste[b] == true)	{
				System.out.print((b+1)+" ");
				zeichenzaehler++;
		    if(zeichenzaehler%5 == 0)		
            System.out.print("\n");        
			}
         b++;
		}   
      
                                      
		//Primfaktorzerlegung von n
      int zaehler = 0;
		System.out.print("\n"+n+" = ");

		while(c < n){
         if(liste[c] == false){
            c++;
            continue;
         }
        	if((n%(c+1)) == 0){
           if(zaehler != 0)
             System.out.print(" * "+(c+1));
           if(zaehler == 0){
             System.out.print(c+1);
             zaehler++;
           }
			  n = n/(c+1);           
			}
         else
            c++;
		}
      System.out.print("\n");
	}
}

 

[Spacerat]

Das Thema gab's in diesem Forum schon öfters... Suchbegriffe "Erastothenes" und/oder "Pimzahl" in die SuFu gehackt sollten da bereits helfen.
Ansonsten... in einer Methode "isPrime(Number n)" kann man zwei Dinge von vorne herein ausschliessen:
1. "== 2" gibt true zurück
2. "% 2 || < 2" gibt false zurück.

Dann nimmt man von n die Wurzel als Obergrenze der Teiler und dann in einer Schleife:

for(int t = 3; t < Math.sqrt(n); t += 2) {
  if(n % t == 0) {
    return true;
  }
}
return false;

Wenn "isPrime()" true liefert, speicherst du die Zahl in einer Liste, bei false teilst du die Zahl durch die Werte in der Liste und prüfst erneut. Das ganze solange, bis das Teilergebnis selbst eine Primzahl ist.
Wenn mann's geschickt anstellt, geht das alles problemlos in einer einzigen Methode, denn eigentlich reichen als Teiler die Zahlen (Primzahlen) in der Liste völlig aus. Die Liste muss jedoch erst mal vorbefüllt sein (z.B. mit 2, 3, 5 und 7) und darf anschliessend keine Lücken aufweisen (also Primzahlen auslassen, z.B. auf die 7 muss die 11 und nicht die 13 folgen).

 

[m4libu17]

DAFUQ?
"In einer Methode kann man..."

Was für ne Methode?
Wie ich schon sagte...ich lern das seit Oktober und hab keine Ahnung von Methoden oder dergleichen.
Ich war bisher schon froh dass es ÜBERHAUPT n Ergebnis geliefert hat!

 

[pappawinni]

Wenn Sieb des Eratosthenes gefragt ist, sollte man das dann vielleicht auch machen.
Auch wenn andere Methoden vielleicht einfacher oder schneller sind...

Ich würd das vielleicht so lösen:

import java.util.ArrayList;

public class Bsp07 {
	 
    public static void main(String[] args) {
        
          int n=args.length==0? 100: Integer.parseInt(args [0]);

          ArrayList<Integer> primzahlen = eratosthenes(n);
          ArrayList<Integer> faktoren = new ArrayList<Integer>();
          int rest = n;
          int j;
          for (int i = 0;i < primzahlen.size(); i++){
        	  j = primzahlen.get(i);
        	  while (rest % j == 0){
        		  rest /= j;
        		  faktoren.add(j);
        	  }
        	  if (rest==1) break;
          }

          System.out.println("Primzahlen bis " + n);
          printList(primzahlen);
          
          System.out.println("Primfaktoren für " + n);
          printList(faktoren);

    }

    private static ArrayList<Integer> eratosthenes(int n){
        
        boolean[] gestrichen = new boolean[n-1];
        ArrayList<Integer> primes = new ArrayList<Integer>();
        for (int i = 2; i <= n; i++) {
        	gestrichen[i-2] = false;	
        }
        int q = (int) Math.sqrt(n);
        for(int i=2; i <= n; i++) {
            if (!gestrichen[i-2]) {
            	primes.add(i);
                if (i <= q) {
                    for (int j = i*i; j <= n; j+=i) {
                  	  if (j <= n) gestrichen[j-2]=true;
                    }
                }
            }
        }
        return primes;
    }

    private static void printList(ArrayList<Integer> intList) {
        int i=0;
        for (int entry:intList){
        	System.out.printf("%20d",entry);
        	i++;
        	if (i%5 == 0) System.out.println();
        }	        	
        System.out.println("\n");	    	
    }
}

 

[m4libu17]

das sind alles sachen die bisher nicht behandelt wurden ... deswegen geh ich davon aus dass wir das auch ohne lösen sollen

 

[AmunRa]

Nur so als NEbeninfo, für die tatsächliche implementierung des Siebes des Eratosthenes braucht man keine modulo rechnung.

Vl errinnert sich der eine oder andere daran, dass an das in der Volkschule oder halt in der 5 Schulstufe gelernt hat nur mit Zettel und Stift. Imprinzip ist das genau das was pappwini schon geschrieben hat, aber vl versteht man es so besser.

SChritt 1: BoolArray anlegen mit der Lenge n+1 nennen wir es notPrime (*) 
     alle Werte in diese Array sind nun false
Schritt 2: setze notPrime[0] = true;
Schritt 3: Wenn 1 als nicht als Primzahl zählt setze notPrime[1]= true
Schritt 4: 
  for ( int i=2;i<n+1/2;i++){
     if (!notPrime[i]){ //also wenn der Wert an dieser Stelle eine Primzahl ist
         for (int j=i+i;i<n+1;j=j+i){
              notPrime[j] = true;
         }
  }

SChritt 5 einmal durch das Array durch laufen und jede Stelle die false ist ist eine Primzahl und kann daher in eine Liste eingetragen werden.

(*) Ich nehme hier n+1 sodass die IndexPosition 3 auch tatsächlich die Zahl 3 meint und daher die Zahl n auch tatsächlich die Indexposition n hat.


Das ist der wirkliche Sieb des erathostenes Algorithmus und kommt vollständig ohne modulo Operation aus

Lg
AmunRa

 

[pappawinni]

Das Ganze mal mit Array statt Arraylist und als "all-in-one" Methode

    public static void main(String[] args) {
        
          int n = args.length==0 ? 100: Integer.parseInt(args [0]); //Liest Wert ein
          // Hier vielleicht noch eine Überprüfung, ob n im gültigen Bereich liegt

          // Eratosthenes
          boolean[] gestrichen = new boolean[n-1];
          int z = 0;
          for (int i = 2; i <= n; i++) {
          	gestrichen[i-2] = false;	
          }
          int q = (int) Math.sqrt(n);
          for(int i=2; i <= n; i++) {
              if (!gestrichen[i-2]) {
              	z++;
                  if (i <= q) {
                      for (int j = i*i; j <= n; j+=i) {
                    	  if (j <= n) gestrichen[j-2]=true;
                      }
                  }
              }
          }
          int[] primzahlen = new int[z];

          System.out.println("Primzahlen bis " + n);
          z=0;
          for(int i=2; i <= n; i++) {
              if (!gestrichen[i-2]) {
              	primzahlen[z]=i;         	
                z++;
            	System.out.printf("%20d",i);
            	if (z%5 == 0) System.out.println();
              }
          }
          System.out.println();
          
          // Primfaktoren , benutzt Ergebnis von Eratosthenes
          System.out.println("Faktoren für " + n);
          int rest = n;
          int j;
          z=0;
          for (int i = 0;i < primzahlen.length; i++){
        	  j = primzahlen[i];
        	  while (rest % j == 0){
        		  rest /= j;
        		  z++;
        		  System.out.printf("%20d",j);
        		  if ( z%5 == 0 ) System.out.println();
        	  }
        	  if (rest==1) break;
          }
          System.out.println();

    }

 

[m4libu17]

ok ... ich hab keine ahnung was printf genau macht und habs dewegen einfach mal in ein normales print umgeformt ... das ausgabeformat ist ziemlich genau vorgegeben

aber der letzte code von pappawinni sieht doch schon für mich als anfänger sehr viel verständlicher aus.
was ich mich jetzt noch frage ist: wieso ist der code so viel leistungsstärker als meiner ... ich dachte wenn man schleifen in schleifen setzt dass das so viel leistung kostet?

 

[AmunRa]

Es geht bei pappawanis block nicht direkt um effizienz, sondern darum, dass das eine iplementierung des siebes des erath...
ist während dein Code dies nicht ist.

du verwendest zur untersuchung ob eine Zahl eine Primzahl ist die modulo Operation.


eine SChleife in einer Schleife muss nicht umbedingt langsamer sein.

Wenn ich z.B. mit deinm Algorithmus die schleifendurchläufe Zähle komme ich für n = 40 also alle ZAhlen bis 40 auf ueber 300 schleifen durchläufe, während bei pappas version die innerer SChleife nur 34 mal ausgeführt wird.

Das spricht für eine effizientere implementierung als deine ( DIe ich erhlich gesagt bis jetzt nicht verstanden habe).

 

[m4libu17]

wenn ich mir das so ansehe fällt der unterschied langsam auf ...

bei meinem Algorithmus wird jede (bzw jede zweite) zahl geprüft,
während bei pappawinni alle vielfachen einer bereits gefundenen Primzahl einfach übersprungen werden ... dass war eigentlich das was ich versucht habe... erfolglos

in diesem sinne danke ich euch für eure (erfolgreiche) Hilfe und dafür dass ihr mir meine fragen beantwprtet habt

 

[pappawinni]

printf ist halt gerade eben für die formatierte Ausgabe, aber das kannst du ja selbst googlen, oder?

in Kurzform:
der erste Parameter von printf ist der auszugebende Text, wobei Platzhalter eingebaut werden können.
Solche Platzhalter beginnen mit dem %-Zeichen..
"%20d" bedeutet halt, dass hier eine Zahl rechtsbündig in 20 Zeichen eingesetzt ausgegeben werden soll.
Für einzusetzende Werte müssen dann auch entsprechende Parameter in der erforderlichen Reihenfolge angegeben werden.
"%n" wäre eine Zeilenvorschub, wofür natürlich kein Parameter erforderlich ist.

Für weitere Erläuterungen hab ich jetzt leider keine Zeit.