Sieb des Eratosthenes ohne boolean

[CopyPaste]

Hey Leute,
ich habe folgende Aufgabe zu lösen und ich komme bei einer Kleinigkeit nicht weiter.
Ich soll mit Hilfe des Siebes des Eratosthenes ein Array mit einer benutzerbestimmten Länge nach Primzahlen filtern und dann ausgeben.

Vorgaben sind drei Methoden zu erstellen nach folgendem Muster:
1. int[] anlegenEinesArrays -->Bentzer gibt n an - Array soll mit den Zahlen von 2 bis n+1 befüllt werden
2. int[] siebDesEratosthenes(int[] zahlen)
3. void ausgabe(int[] zahlen)

main methode:

  public static void main(String[] args) {
        int[] zahlen = anlegenEinesArrays();
    	zahlen = siebDesEratosthenes(zahlen);
    	ausgabe(zahlen);
  }

es scheint bei mir in einer der Schleifen der siebDesEratosthenes Methode zu scheitern.
hab schon einiges versucht und das ist nur eine der falschen versuche 😀

public static int[] siebDesEratosthenes(int[] zahlen) {
		int k=2;
		for (int i = 2; i < zahlen.length;i++) {
			if (zahlen[i-2] != 0) {	
				for (int j = k*i;j < zahlen.length; k++) {
					zahlen[j-2] = 0;
				}
			}
		}
		return zahlen;
}

Eine zweite Idee wäre:

public static int[] siebDesEratosthenes(int[] zahlen) {
		for (int i = 2; i < zahlen.length;i++) {
			if (zahlen[i] != 0) {	
				for (int j=2; i*j < zahlen.length; j++) {
					zahlen[i*j] = 0;
				}
			}
		}
		return zahlen;
}

Scheint der Lösung schon näher zu sein, jedoch gibt er einige nicht Primzahlen mit aus.
Das spuckt er aus für die Eingabe von 80 oO
2, 3, 4, 5, 7, 9, 13, 15, 19, 21, 25, 31, 33, 39, 43, 45, 49, 55, 61, 63, 69, 73, 75, 81,



Hoffe ihr könnte mir sagen wie es richtig sein muss. Ich weiß, dass die jetzige Schleife Quatsch ist 😛

 

[pappawinni]

Schreib dir doch erstmal auf, wie du genau vorgehen willst.
Sowas nennt sich Pseudocode.
Wenn du dir das dann gut überlegt hast, dann programmiere das.
Wenn dann nicht heraus kommt, was herauskommen soll, musst du halt prüfen,
ob das an deiner Codierung oder an deinem Entwurf liegt.
Beschreibe doch mal wenigstens, was du dir gedacht hast, als du deinen Code hier verbrochen hast.

 

[CopyPaste]

Okay ich versuch mich mal auszudrücken 😀

Als erstes brauche ich eine for-Schleife um die Zahlen im Array durchzugehen
-Start bei Index 0, welches den Wert 2 hat und Ende bei n
-in der Schleife wird mit einer if abfrage geprüft, ob der Zahl im Index i ein Wert != 0 zugeordnet wurde
-das ist wichtig, da später schon mehrere Zahlen durch die zweite for-Schleife auf 0 gesetzt werden -->keine Primzahlen
-in der zweiten for-Schleife sollen nun den Vielfachen der zu prüfenden Zahlen von zahlen der Wert 0 gegeben werden
Somit sollten nach dem ersten Durchlauf alle Vielfachen der 2 zu einer 0 gemacht werden und danach wird das ganze mit der 3 durchlaufen.
Ich denke, dass meine zweite Lösung dem schon sehr nahe ist, jedoch klappt es dennoch nicht

Ich weiß, das ist kein normaler Pseudocode, aber ich hab das Gefühl, so konnte ich mich verständlicher ausdrücken 😛

Von mir aus muss nicht sofort die Lösung genannt werden, aber ein guter Tip der in die richtige Richtung führt wäre nett. 🙂

 

[trääät]

so wird das nicht hinhauen ...

1) der index beginnt bei "0"
2) du hast aber "2" als start-wert ... beginnst also erst beim 3. element ... was den inhalt "4" hat ... darum wird auf jeden fall die 4 drin stehen bleiben ... denn du rechnest ja "2*2" was dann das 5. element ist

ergo : du musst grundsätzlich bei "0" anfangen das array durchzugehen ... nicht erst bei "2" ...

außerdem beißt sich das trotzdem mit deinem vorhaben "ohne bool" denn dein IF ist ein bool .. und auch die runden-bedingungen der loops sind bools ...

also wäre vielleicht auch mal interessant was du mit "ohne bool" meinst ... denn ohne irgendeine art von bool-prüfung wird das nicht möglich sein

 

[CopyPaste]

Ja hast recht, jedoch entsteht dann das Problem, dass für i=0 im ersten Durchlauf dann 0*k gerechnet wird und dann immer 0 rauskommen wird, selbst wenn k dauernd erhöht wird, oder sehe ich da was falsch? Deswegen kam ich ja erst auf den Unsinn mit i=2 😀

Ohne boolean meine ich nur, dass wenn man bei google mal schaut,es fast nur boolean-Arrays für diese Aufgabe gibt und dann am Anfang allen Werten im Array true zugeordnet wird und dann mit der Schleife, die ich versuche hinzukriegen den nicht-Primzahlen false zuzuordnen. Zum Schluss werden dann alle true Werte ausgegeben.

Das ganze muss ich anstatt mit false mit != 0 hinbekommen und alle nicht-Primzahlen 0 werden lassen.
Zum Schluss dann alle Werte !=0 im Array ausgeben.

Das ist ärgerlich, denn ansonsten hätte ich die Lösung vllt schon längst nachvollziehen können -.-

 

[träät]

naja gut ...
aber ob ich nun true oder false in ein bool-array schreibe oder "0" bzw "x" macht keinen unterschied ...

 

[pappawinni]

Also das Sieb hatten wir ja erst..
http://www.java-forum.org/hausaufgaben/143775-primzahlen.html#post962995

und das ein bischen umgebogen sieht dann so aus:

public class Primes{
    // Sieb des Eratosthenes 
     
    public static void main(String[] args) {
        
        int n = args.length==0? 4000 : Integer.parseInt(args [0]);;
        int z= 0;
        int[] primes = new int[n-1];
        
        for (int i = 2; i <= n; i++) {
            primes[i-2] = i;    
        }
        
        for(int i=2; i <= n; i++) {
            if (primes[i-2]>0) {
                z++;
                System.out.println(primes[i-2] + " is Prime No. "+z);
                if (i <= Math.sqrt(n)) {
                    for (int j = i*i; j <= n; j+=i) {
                        if (j <= n) primes[j-2]=0;
                    }                                       
                }
            }
        }
    }
}

Inwieweit das nun mit deiner Aufgabenstellung harmoniert, darfst du selbst herausfinden.

 

[CopyPaste]

Sollte schon etwas anders aussehen, aber ich denke ich habs nun hinbekommen:

public static int[] siebDesEratosthenes(int[] zahlen) {
		for (int i = 0; i < zahlen.length; i++) {
			if (zahlen[i] != 0) {
				for (int j = i + zahlen[i]; j < zahlen.length; j = j + zahlen[i]) {
		                        zahlen[j] = 0;
				}
			}
		}
		return zahlen;
}

Haut soweit hin, nur gehts wahrscheinlich deutlich schöner 😉

 

[hüteüberhüte]

Wenn ohne boolean, warum nicht mit LinkedList (oder wäre das zu langsam)?:

        final int n = 97;
        List<Integer> l = new LinkedList<Integer>();
        for (int i = 2; i <= n; i++) {
            l.add(i);
        }

        a:
        for (int i = 0; i < l.size();) {
            final int j = l.get(i);
            final int sqrt = (int) Math.sqrt(j);
            Iterator<Integer> iter = l.iterator();
            int k;
            while ((k = iter.next()) <= sqrt) {
                if (j % k == 0) {
                    l.remove(i);
                    continue a;
                }
            }
            i++;
        }

        System.out.println("l = " + l);

Für Primzahlen bis 97 funktionierts zumindest...

 

[Landei]

Weil das kein Sieb ist, sondern im Prinzip simple Probedivisionen, also viel aufwendiger. Das Sieb streicht dagegen Vielfache, wenn du modulo rechnest, machst du etwas falsch.

Eine genaue Erklärung findet sich hier (allerdings mit Haskell-Code): http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

 

[hüteüberhüte]

Achso, Vielfache von Primzahlen, richtig? Habe das "Sieb" auch nicht mehr so genau in Erinnerung. Danke für den Hinweis. (Wäre das mit Probedivision denn nicht genau so schnell/aufwändig?)

 

[Landei]

Wäre das mit Probedivision denn nicht genau so schnell/aufwändig?

Nö. Auch wenn das nicht unbedingt intuitiv ist. Aber das genannte Paper rechnet dir die Komplexität vor.

 

[hüteüberhüte]

Hat ja auch keiner gesagt, dass das trivial ist. 😀 Aber nö, keine Lust, das jetzt durchzuackern. 😀 CopyPaste hat ja bereits Lösung.

 

[hüteüberhüte]

Also entweder ich verstehe das Paper nicht richtig, oder da steht, das Sieb benötigt für 50k 900 Millionen irgendwas und die einfache Divisionsmethode für dieselbe Größe 30 Millionen irgendwas.

 

[Landei]

Der englische Wikipedia-Artikel sagt auch etwas in der Richtung, beruft sich aber - oh Wunder - wieder auf das Paper.

 

[hüteüberhüte]

Also ich erinnere mich daran deshalb nicht mehr so genau, weil das irgendwann in der 5. / 6. Klasse dran kam: Hier sind Kästchen mit Zahlen von 2 bis 99, streicht alle nicht-Primzahlen / Vielfache, und mir das seither nicht mehr begegnet ist.

Wenn ich nicht ganz daneben liege, hat die (etwas verbesserte) einfache Divisionsmethode eine Laufzeit von sqrt(n)*n/4=O(n*sqrt(n)), aber man weiß ja nicht, in welchen Abständen Primzahlen auftreten. Es gibt ja auch nur einen indirekten Beweis, daß Primzahlen nicht-endlich sind.

 

[bERt0r]

Es reicht wenn man die Vielfachen der Zahlen von 2 bis n/2 streicht.

 

[Ark]

Es reicht wenn man die Vielfachen der Zahlen von 2 bis n/2 streicht.

Es reicht sogar, bis zur Wurzel von n zu gehen (steht auch im Paper).

Ark

 

[bERt0r]

Ja, auf was ich hinauswollte war das hier:

public static void sieb(int[] arr)
	{
		for (int i = 4; i < arr.length; i = i + 2)
		{
			arr[i] = 0;
		}
		
		for (int i = 3; i < Math.sqrt(arr.length); i = i + 2)
		{
			if (arr[i] != 0)
			{
				int j = i;
				while (j * i < arr.length)
				{
					arr[j * i] = 0;
					j = j + 2;
				}
			}
		}
	}

 

[hüteüberhüte]

Hier nochmal die einfache Divisionsmethode:

    private List<Integer> gibPrimzahlen(int n) {
        ArrayList<Integer> l = new ArrayList<Integer>(/*(int) (n * 0.5)*/);
        l.add(2);
        a:
        for (int i = 3; i <= n; i += 2) {
            final int sqrt = (int) Math.sqrt(i);
            for (int j = 3; j <= sqrt; j += 2) {
                if (i % j == 0) {
                    continue a;
                }
            }
            l.add(i);
        }
        return l;
    }

Geht schon recht flott. Wie lang man die Liste wählen sollte, ist aber glaub ich auch unklar.

 

[Landei]

Es gibt ja auch nur einen indirekten Beweis, daß Primzahlen nicht-endlich sind.

Das würde ich so nicht im Raum stehen lassen. Es lässt sich ganz einfach eine unendliche Liste von Primzahlen erzeugen: Nimm alle Primzahlen, die schon in der Liste sind, multipliziere sie, addiere 1 und füge den kleinsten Teiler des Resultats, der größer als eins ist, als neue Primzahl in die Liste ein, z.B.:

2
2+1=3, -> 3 kommt dazu
2*3+1 = 7 -> 7 kommt dazu
2*3*7+1= 43 -> 43 kommt dazu
2*3*7*43+1=1807 -> 13 kommt dazu
...

Demnach kann man eine unendliche Teilmenge (*) aller Primzahlen erzeugen, also muss die Menge aller Primzahlen ebenfalls unendlich sein - ich denke, das kann als direkter Beweis der Unendlichkeit der Primzahlenfolge gelten.

(*) Es wird ja nirgendwo behauptet, auf diese Weise wirklich alle Primzahlen zu "erwischen". Soweit ich weiß, ist die dahingehende Vermutung noch unbewiesen. Mehr zur erzeugten Folge 2,3,7,43,13... unter A000945 - OEIS