# Primzahlen - Sieb des Eratosthenes



## emre.hasan (20. Apr 2009)

Hallo liebe Java-Programmierer,
Ich muss für meine Abiturpräsentation den Sieb des Eratosthenes vorstellen. Jedoch scheitert bei mir der Code ab ca. 93000 ( als Grenze). Nun ist es zwa rnciht wichtig ob ich bis 1. Million zählen lasse oder bis 30 Millionen, doch ist es für mich von persönlicher Interesse rauszufinden, wie ich über meine nicht überschreitbare Grenze komme.

Ich verwende ein Boolean und allgemein überall Integers. Ich weiß das es daran liegen muss warum ich nicht weiterkomme, da ich an einer Stelle (n = die Grenze) n potenziere. Aber ein Array kann man ohne Integer ja auch nicht benutzen. 

Hier der Code. Ich hoffe ihr könnt mir helfen.


```
import java.io.*;

public class Erasto {
    
    public void sieb(int n_grenze)
    {
        
            int n = n_grenze;    // Grenze festlegen
            
            boolean gestrichen[] = new boolean[n+1];    //Array mit n-Elementen erstellen
            
            for(int i = 2; i < n; i++)
                gestrichen[i] = false;
            
            for(int i = 2; i < n/2; i++)
            {
                for(int j = 2; j < n/2 ; j++)
                {
                    if(i*j < n)
                        gestrichen[i*j] = true;
                }
            }
            
            String s = "1, \n";
            
            for(int i = 2; i < n; i++)
            {
                if(gestrichen[i] == false)
                    s += i + ", \n";
            }
            
            System.out.println(s);
            
    }
    
    
    public static void main(String[] args)
    {
        Erasto t = new Erasto();
        t.sieb(92500);
    }
    
    

}
```


----------



## hdi (20. Apr 2009)

Also erstmal


```
boolean gestrichen[] = new boolean[n+1];    //Array mit n-Elementen erstellen
```

ist nicht richtig. boolean[n+1] erzeugt ein Array, in das n+1 booleans passen. Nicht n.

Zu dem Problem: Ich weiss gar nicht ob dein Programm korrekt arbeitet. Ich denke eher nicht. int geht bis maximal 65538 oder so. Du multiplizierst aber zum Teil Zahlen, deren Ergebnis weit drüber ist. Wenn ein Wert in einen int gesteckt wird, der nicht gültig ist, kommt irgendein Rotz raus (er macht Überlauf und fängt von vorne an, also bei -65537 o.ä.).

Ich würde sagen wechsel von int nach long. Oder gleich nach BigInteger


```
Aber ein Array kann man ohne Integer ja auch nicht benutzen.
```

Das stimmt nicht. Wie gesagt: long oder BigInteger (Allgemein kann ein Array aber alles beinhalten, auch Buttertoast)


----------



## Marco13 (20. Apr 2009)

hdi hat gesagt.:


> int geht bis maximal 65538 oder so.


 :noe: :autsch: 
*SCJP 2019* 

2147483647!!!


----------



## emre.hasan (20. Apr 2009)

wenn ich bei Eclipse für int grenze ; long grenze wähle und auch alles auf long umstelle was ich als int benutzte....
da kommt beim boolean ein fehler ( cant convert long to int ( ungefähr). 
Also Arrays doch nur mit ganzzahlen möglich( int's)?


----------



## hdi (20. Apr 2009)

lol  Ja mir kam das auch etwas seltsam vor, aber woher kenn ich diese Zahl mit 65k irgendwas? Das ist doch auch irgendein Limit? Hmm... Naja, das erklärt dann auch das Limit von ~92500. 
Aber nach wie vor: long erhöht das ganze, hab grad keine Lust die Wertebereiche nachzusehen, kann ja Marco sagen 
Und BigInteger kann "unendlich" gross werden. D.h. soviel dein Arbeitsspeicher, bzw der für die JVM reservierte Speicher hergibt.


----------



## emre.hasan (20. Apr 2009)

Bitte gib mir mal ein Code-Beispiel wie mein ein Array mit einem BigInteger deklariert.
Ich krieg da einen Fehler.


----------



## hdi (20. Apr 2009)

Ja sorry, ein Array darf nicht mehr Fächer haben als Integer.MAX_INT. Du kannst dir aber eine Liste machen, die sind dynamisch und *glaube ich* ohne Begrenzung (natürlich wieder die Sache mit dem RAM)


----------



## ModellbahnerTT (20. Apr 2009)

Hi,
das ist natürlich quatsch, arrays kannst du nur mit ints initialisieren, nicht mit longs oder gar BigIntegers.
Die 2147483647 Plätze die du damit addressieren kannst sollten auch erstmal reichen 


> Ja mir kam das auch etwas seltsam vor, aber woher kenn ich diese Zahl mit 65k irgendwas? Das ist doch auch irgendein Limit?


autsch, 65536 ist 2^16 ...


----------



## hdi (20. Apr 2009)

2^16, aber irgendwo kommt diese Zahl doch als Limit von irgendwas vor? Wie bin ich da drauf gekommen...

PS: Ich meinte mit dem long/BigInteger nicht die Grösse vom Array, sondern die Typen mit denen er rumrechnet.


----------



## Ark (20. Apr 2009)

```
BigInteger x = new BigInteger[10];
```
Allerdings funktionieren BigInteger etwas anders als "normale" Ganzzahlen, weil es sich hierbei um Objekte handelt (int und long sind primitive Typen).

Zur Erinnerung die Anzahl voneinander unterscheidbarer Zustände:
byte: 2^8
short/char: 2^16
int: 2^32
long: 2^64

Ark

EDIT@hdi: verkettete Listen sind prinzipiell unendlich, ich weiß aber nicht, ob da eine "Sperre" mit size()<=Integer.MAX_VALUE eingebaut wurde. ArrayLists dagegen sind z.B. durch den int-Raum beschränkt.

Ark


----------



## emre.hasan (20. Apr 2009)

Gibt es also keine andere Möglichkeit meinen Code so umzuformen das ich über 92500 komme?


----------



## hdi (20. Apr 2009)

Nur, indem du dir eine List machst statt einem Array für die verstrichenen Typen, und mit long oder BigInteger rechnest.


----------



## Marco13 (20. Apr 2009)

65536 ist die Grenze für char (unsigned)

BigInteger ist ein bißchen "unhandlich" - man kann damit eben nicht mehr 
a = b + c;
schreiben, sondern muss
a = b.add(c);
und so machen. 

Bringt in diesem Fall auch nicht viel: int geht wie gesagt bis 2 Milliarden... d.h. wenn du das mit dem Sieb ausrechnen willst, wirst du da nicht nur ein Speicherproblem kreigen, sondern auch damit, dass Arrays in Java AFAIK nur eben diese 2 Milliarden Einträge haben dürfen (da müßte man mal einen SCJP fragen :bae: )

So, wie du es im Moment geschrieben hast, ist es etwas ... ungünstig programmiert: Die beiden Schleifen laufen bis n/2, d.h bei deinen 90000 Elementen laufen die Schleifen bis ca. 45000, und bei 45000*45000 kommt dann MEHR als 2 Milliarden raus, es tritt der angesprochene Überlauf auf, und der Index wird negativ.

Überleg' nochmal, ob die beiden Schleifen so wirklich richtig sind. Am besten mal auf Karopapier bis ... 30 oder so... aufmalen....


----------



## emre.hasan (20. Apr 2009)

Ihr versteht es i.wie alle falsch....ich weiß das ich mit double und anderen Datentypen über die 92500 komme. 
Mir geht es aber darum das Array eines BOOLEANS zu benutzen. Und das Index des Booleans kann doch nur mit Integer angegeben werden.oder ist die Dokumentation von Sun falsch?


----------



## ModellbahnerTT (20. Apr 2009)

hdi hat gesagt.:


> 2^16, aber irgendwo kommt diese Zahl doch als Limit von irgendwas vor? Wie bin ich da drauf gekommen...
> 
> PS: Ich meinte mit dem long/BigInteger nicht die Grösse vom Array, sondern die Typen mit denen er rumrechnet.


autsch2, ja das Limit für alles Zahlen mit 16 bit...

Wieso sollte er überhaupt Zahlen im Array speichern. Mehr als einen boolean Wert braucht er doch nicht. Im übrigen ist ein boolean Array von anfang an mit false-es vorbelegt, die erste Schleife ist also überflüssig.


----------



## emre.hasan (20. Apr 2009)

boolean gestrichen[] = new boolean[n+1];

Es geht doch nur um diesen Teil. da 92500^2 über der Integergrenze ist.

boolean[int]. Kann man anstatt [int] hier ein [biginteger] nehmen nein oder? gibt es andere möglichkeiten wie ich auf meine zahlen komme?


----------



## Marco13 (20. Apr 2009)

Wow - 3 Posts gleichzeitig :shock: richtig was los hier.

Nein, es stimmt schon: Ein Arrayindex kann nur ein int sein, und mit dem Sieb wirst du nicht ohne Verrenkungen über 2 Milliarden kommen. Deine Schleifen stimmen so einfach nicht.


----------



## ModellbahnerTT (20. Apr 2009)

Um zum Thema zurückzukehren, die innere Schleife sollte evtl. nicht bis n/2 sondern bis n/i laufen.


----------



## emre.hasan (20. Apr 2009)

Gibt mir dann doch bitte Ideen wie ich das verändern könnte....


----------



## Marco13 (20. Apr 2009)

Entweder...


Marco13 hat gesagt.:


> Überleg' nochmal, ob die beiden Schleifen so wirklich richtig sind. Am besten mal auf Karopapier bis ... 30 oder so... aufmalen....


...oder den Code von Sieb des Eratosthenes ? Wikipedia (richtig) abtippen...


----------



## emre.hasan (20. Apr 2009)

Marco. mein lehrer hat mir auch diesen Pseudo-Code gegeben.

Es löst trotzdem nciht das Problem mit dem "begrenzten Integer-Boolean-Array"
Mein Code funktioniert. Ich habe die erste Schleife nun gelöscht, da sowieso die Arrays am Anfang auf Null gesetzt sind. Die zweite Schleife läuft jezt auch bis i, da der Durchlauf bis n/2 nur Zeitverlust wäre. und NU?


----------



## hdi (20. Apr 2009)

Also wenn du denkst der Code passt, und du errichst das integer-limit, dann kann ich nur ein drittes mal sagen: Nimm eine Liste von Booleans. Die sind dynamisch und haben - theoretisch -  keine maximale Länge. Bevor jetzt aber ModellBahnerTT mit einem *AUTSCH3* reinfetzt, sage ich mal lieber: Ich glaube, dass das so ist. Siehe API für mehr.


----------



## Marco13 (20. Apr 2009)

Es gibt auch einen Einfacheren Prinzahl-Test

```
for (int i=3; i<8; i++)
{
    if (i%2==1) System.out.println(i+" ist prim");
}
```
Hab's gerade getestet, und funktioniert.

Aber ernst beiseite: Entweder der Pseudocode deines Lehrers ist falsch, oder du hast ihn falsch implementiert. Das von Wikipedia (bevor ich mich hier lange aufhalte)

```
import java.io.*;

public class Erasto {

    public void sieb(int n_grenze)
    {

            int n = n_grenze;    // Grenze festlegen

            boolean gestrichen[] = new boolean[n+1];    //Array mit n-Elementen erstellen

            int i = 2;
            while (i*i <= n)
            {
                if (!gestrichen[i])
                {
                    // i ist prim, streiche seine Vielfache mit i*i beginnend:
                    for (int j = i*i; j<=n; j+=i)
                    {
                        gestrichen[j] = true;
                    }
                }
                i = i+1;
            }
            String s = "1, \n";

            for(i = 2; i < n; i++)
            {
                if(gestrichen[i] == false)
                    s += i + ", \n";
            }

            System.out.println(s);

    }


    public static void main(String[] args)
    {
        Erasto t = new Erasto();
        t.sieb(200);
    }



}
```
an die 200 kannst du auch noch ein paar nullen dranhängen. Irgendwann musst du mit
java -Xmx1000m Erasto
starten, damit der Speicher reicht...


----------



## Marco13 (20. Apr 2009)

hdi hat gesagt.:


> Also wenn du denkst der Code passt, und du errichst das integer-limit, dann kann ich nur ein drittes mal sagen: Nimm eine Liste von Booleans. Die sind dynamisch und haben - theoretisch -  keine maximale Länge. Bevor jetzt aber ModellBahnerTT mit einem *AUTSCH3* reinfetzt, sage ich mal lieber: Ich glaube, dass das so ist. Siehe API für mehr.



Das AUTSCH3 kommt jetzt mal von mir: Erstens ist das arg langsam, und zweitens gibt's da in bezug auf die Grenze von 2 Milliarden noch einen kleinen Stolperstein: List (Java Platform SE 6)


----------



## hdi (20. Apr 2009)

Jo ich sag ja er soll API kucken  Ach sorry, ich hätte gar nich erst anfangen sollen mich hier einzumischen. Ich behaupte hier irgendwelche Sachen die ich nur rate weil ich zu faul bin nachzusehen. Sorry, ich geh mal lieber ins Bett


----------



## emre.hasan (20. Apr 2009)

danke für alle antworten


----------



## SebiB90 (20. Apr 2009)

hdi hat gesagt.:


> 2^16, aber irgendwo kommt diese Zahl doch als Limit von irgendwas vor? Wie bin ich da drauf gekommen...



Wenn ich mich nicht irre, ist das außerdem die Maximale Länge es Text Feldes in einer MySQL Datenbank oder?
Zudem waren Integers früher 2^16. Halt noch bei 16bit Systemen. Ich glaub bei Visual Basic ist int noch 2^16.


----------



## 0x7F800000 (21. Apr 2009)

```
gestrichen[i*j] = true;
```
sowas ist im sieb des Eratosthenes gröbster unsinn (wofür steht übrigens "Erasto" :autsch
Dieser Sieb multipliziert nirgends was. Damit dieser Sieb läuft, muss man nur true/false ablesen und addieren können. Wenn sich irgendwo multiplikationen ohne guten grund reinschleichen, dann muss da irgendwas faul sein.

Wenn du speicherplatz sparen willst, kannst du folgende maßnahmen ergreifen:
1) alle geraden zahlen weglassen, diese dauernd zu prüfen ist echt etwas witzlos
2) alle durch 2 und 3 (und evtl. auch 5,7...) teilbaren zahlen von anfang an weglassen. Das ist schwierig, weil die abstände zwischen den übrigbleibenden zahlen ein zunehmend komplizierteres muster aufweisen, das ist dann ein wenig trickreich diese Lücken korrekt zu überspringen
3) statt boolean[n] könntest du long[n/64] allokieren, und einzelne bits von longs zur markierung prim/nicht prim benutzen. Das ist schonmal 8 mal kompakter, als mit booleans, allerding geht da die performance wohl ordentlich in den keller.
4) statt einem array (deren Länge durch Integer.MAX_VALUE) beschränkt ist, könntest du einfach mehrere Arrays nebeneinander allokieren.

Damit könntest du die Obergrenze... hm... so um Faktor 1000 verbessern? Allerdings macht es dann wohl weniger Spaß, auf ein ergebnis zu warten, weil das für einen Haushaltsüblichen PC einfach ziemlich viel Holz ist.


----------



## ModellbahnerTT (21. Apr 2009)

hdi hat gesagt.:


> Also wenn du denkst der Code passt, und du errichst das integer-limit, dann kann ich nur ein drittes mal sagen: Nimm eine Liste von Booleans. Die sind dynamisch und haben - theoretisch -  keine maximale Länge. Bevor jetzt aber ModellBahnerTT mit einem *AUTSCH3* reinfetzt, sage ich mal lieber: Ich glaube, dass das so ist. Siehe API für mehr.


Das autsch3 kommt erstmal, weil du das Problem anscheinend nicht verstanden hast. Hättest du nicht damit angefangen zu behauten das Array sein zu klein hätten wir uns hier eine Seite an Posts sparen können.



0x7F800000 hat gesagt.:


> ```
> gestrichen[i*j] = true;
> ```
> sowas ist im sieb des Eratosthenes gröbster unsinn (wofür steht übrigens "Erasto" :autsch
> ...


Hast du den Algorithmus irgendwie nicht verstanden?


----------



## faetzminator (21. Apr 2009)

0x7F800000 hat gesagt.:


> [...]
> 1) alle geraden zahlen weglassen, diese dauernd zu prüfen ist echt etwas witzlos
> 2) alle durch 2 und 3 (und evtl. auch 5,7...) teilbaren zahlen von anfang an weglassen. Das ist schwierig, weil die abstände zwischen den übrigbleibenden zahlen ein zunehmend komplizierteres muster aufweisen, das ist dann ein wenig trickreich diese Lücken korrekt zu überspringen
> [...]



Du meinst dann wohl Sieb des Atkin ? Wikipedia, da findet man alle Regeln bezüglich des Streichens.


----------



## emre.hasan (21. Apr 2009)

So... Ich merke wirklich immer mehr wir reden fast einander vorbei. Mein lehrer will den sieb des eratostehenes! Der code gibt mir die richtigen primzahlen aus also kann ich nicht viel falsch gemacht haben. 
Der tipp mit einem long array hilft mir immer noch nicht da ich das index der arrays fur grosse zahlen brauche deren wert ich im index eines boolean arrays speichere wie es der algorithmus auch vorsieht.und auch dieser ware trotzdem ein 'integer'. Ich muss i*j nehmen fur ALLE vielfachen bis von j bis i.

Eine idee scheint mir bisher am sinnvollsten. Wie kann ich zwei arrays sozusagen miteinander verbinden? Wie kann ich dem zweiten array erzahlen das er ab 9250'1' anfangt?
Sorry furs nerven.


----------



## faetzminator (21. Apr 2009)

emre.hasan hat gesagt.:


> So... Ich merke wirklich immer mehr wir reden fast einander vorbei. Mein lehrer will den sieb des eratostehenes!



hättest du au nur die ersten zwei Sätze des Links gelesen, wüsstest du, das Aktin nur eine Optimierung von Eratosthenes ist 


> Ich muss i*j nehmen fur ALLE vielfachen bis von j bis i.


das ändert die Situation wieder...


> Eine idee scheint mir bisher am sinnvollsten. Wie kann ich zwei arrays sozusagen miteinander verbinden? Wie kann ich dem zweiten array erzahlen das er ab 9250'1' anfangt?


du machst ein zweidimensionales Array, mit welchem du dann per

```
array[einSehrGrosserIndex / MAX][einSehrGrosserIndex % MAX]
```
zugreifen kannst.


----------



## emre.hasan (21. Apr 2009)

Danke ich werds mal versuchen heut nachmittag. Hoffe ich komme so nicht uber die integergrenze


----------



## Ark (21. Apr 2009)

emre.hasan hat gesagt.:


> Danke ich werds mal versuchen heut nachmittag. Hoffe ich komme so nicht uber die integergrenze


Vorher wird wahrscheinlich dein Speicher explodiert sein - es sei denn, du hast mindestens 9 GB Arbeitsspeicher. (Oder habe ich das etwas falsch vestanden?)

Im Übrigen ist das Sieb im Deutschen sächlich und nicht männlich.

Ark


----------



## 0x7F800000 (21. Apr 2009)

ModellbahnerTT hat gesagt.:


> Hast du den Algorithmus irgendwie nicht verstanden?


Öhm, wenn dir irgendwo ein Fehler aufgefallen ist, wäre es deinerseits sehr freundlich, wenn du auf die konkrete Zeile hinweisen würdest, statt den gesammten Beitrag zu zitieren. Im großen und ganzen hat mein Beitrag imho schon mehr oder weniger was mit dem Sieb des Eratosthenes zu tun ???:L


----------



## Marco13 (21. Apr 2009)

emre.hasan hat gesagt.:


> Sorry furs nerven.



Im Moment stört mich höchstens, weil du die gegebenen Hinweise nicht berücksichtigst - aber es stimmt schon, dass dieser Thread ... naja ... nicht gerade "repäsentativ" für dieses Forum ist - normalerweise sind die Hilfen gezielter, sachlicher und ... richtiger... Aus DIESEM Thread die Hinweise rauszufiltern, die man berücksichtigen sollte, ist etwas schwierig. 

Aber nochmal:



emre.hasan hat gesagt.:


> Der tipp mit einem long array hilft mir immer noch nicht da ich das index der arrays fur grosse zahlen brauche deren wert ich im index eines boolean arrays speichere wie es der algorithmus auch vorsieht.und auch dieser ware trotzdem ein 'integer'. Ich muss i*j nehmen fur ALLE vielfachen bis von j bis i.



Wenn du die Zahlen von 1 bis 90000 im Sieb-Array markieren willst, darfst du NICHT mit i und j bis jeweils 45000 laufen - wenn man dann i und j miteinander multipliziert, kommt >2 Milliarden raus. Wenn du wirklich NUR die Felder markieren würdest, die du markieren musst, dann würde dort keine Zahl rauskommen, die größer ist als 90000. Es geht ja nicht um irgendwelche Arraygrößen, sondern nur darum, dass die _Indizes_ für den Arrayzugriff nicht stimmen.

Oder nochmal ganz kompakt: *Deine Schleifen sind falsch*.

So. Macht was draus 


@ModellbahnerTT: War das letzte eine rethorische Frage?  Wie man am geposteten Code sieht, braucht man die Multiplikation i*j nicht, von daher war 0x7F800000's Einwand gerechtfertigt.


----------



## SebiB90 (21. Apr 2009)

Also, hab nicht den ganzen Thread jetzt gelesen, aber:


Marco13 hat gesagt.:


> @ModellbahnerTT: War das letzte eine rethorische Frage?  Wie man am geposteten Code sieht, braucht man die Multiplikation i*j nicht, von daher war 0x7F800000's Einwand gerechtfertigt.



Das ist nicht ganz richtig. Es geht sowohl mit multiplikation als auch mit addition. Ob man nun ne Schleife macht, die bei j=2 und i=2 startet und dann bei jedem durchgang j um i erhöht und j anschließend als index benutzt oder man j in einer schritten hochzählt und dann mit i multipliziert ist egal. Allerdings hat es beim ersten Code im Startbeitrag nicht funktioniert, weil man die innere Schleife nur durchlaufen darf, wenn die Zahl nicht weggestrichen ist.


----------



## Marco13 (21. Apr 2009)

SebiB90 hat gesagt.:


> Das ist nicht ganz richtig. Es geht sowohl mit multiplikation als auch mit addition.



Was ist nicht richtig? ???:L Ich hatte nie gesagt, dass mit Multiplikation nicht geht. Es ging nur darum, dass man keine Multiplikation braucht, und man sie, wenn sie so einfach zu vermeiden ist, auch vermeiden sollte (da sie zumindest theoretisch mehr Rechenaufwand benötigt).


----------



## emre.hasan (21. Apr 2009)

Danke fur die grammatik verbesserung in der deutschen sprache. Das ist mir sehr wichtig danke. Ist immer wichtig fur einen muttersprachler einer sprache die keine bestimmten artikel kennt. Wie auch immer ich les mich mal nochmals durch das forum durch und versuch eure ratschlage zu befolgen. Vielen dank


----------



## 0x7F800000 (21. Apr 2009)

SebiB90 hat gesagt.:


> Es geht sowohl mit multiplikation als auch mit addition. Ob man nun ne Schleife macht, die bei j=2 und i=2 startet und dann bei jedem durchgang j um i erhöht und j anschließend als index benutzt oder man j in einer schritten hochzählt und dann mit i multipliziert ist egal.


egal? Multiplikation ist komplexer als Addition, also wird es entweder lahmer ausgeführt, oder es frisst mehr strom... Selbst wenn diese beide effekte in der Praxis völlig vernachlässigbar sind, hat da die Multiplikation trotzdem nichts zu suchen, weil es den code unnötig komplex macht und den Sinn verschleiert.


----------



## Leroy42 (22. Apr 2009)

emre.hasan hat gesagt.:


> Ihr versteht es i.wie alle falsch....ich weiß das ich mit double und anderen Datentypen über die 92500 komme.
> Mir geht es aber darum das Array eines BOOLEANS zu benutzen.



Warum benutzt du nicht einfach Instanzen der Klasse BitSet? :noe:


----------

