Primzahlen - Sieb des Eratosthenes

[emre.hasan]

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]

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]

int geht bis maximal 65538 oder so.

:noe: :autsch:
SCJP 2019

2147483647!!!

 

[emre.hasan]

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]

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]

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

 

[hdi]

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]

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]

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]

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]

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

 

[hdi]

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

 

[Marco13]

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]

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]

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]

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]

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]

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

 

[emre.hasan]

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

 

[Marco13]

Entweder...

Ü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]

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]

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]

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]

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]

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]

danke für alle antworten

 

[SebiB90]

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]

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]

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.

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.

Hast du den Algorithmus irgendwie nicht verstanden?

 

[faetzminator]

[...]
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]

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]

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]

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

 

[Ark]

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]

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]

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:

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]

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

@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]

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]

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]

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]

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: