Sieb des Eratosthenes (bis 65536)

[Psynox]

Ich muss im Rahmen eines Praktikums ein Programm, zur Überprüfung von Primzahlen, schreiben.
Im Rahmen der Laufzeitoptimierung soll ich es auch auf Basis des 'Sieb des Eratosthenes' schreiben.

Der Algorithmus funktioniert tadellos bis zur Zahl N. Naja fast. Wenn ich bis zur Zahl N=65536 prüfen will steigt er mir ab einer bestimmten Zahl aus, da dessen Vielfaches den maximalen Bereich von int übersteigt. Folglich kommt ein negativer Betrag heraus.

Er will also nun den Array-Key '-21....' true setzen. Doch es gibt keinen Key mit dem Wert '-21....'.

Gibt es eine Möglichkeit dies zum umgehen? Habe ein paar Foren schon durchwühlt doch bisher kam mein Problem nicht vor, anscheinend, oder ich sehe nur nicht mehr richtig :-|, google und die Such-funktion des Forums hier hat mir leider auch nicht weiter geholfen. Ich hoffe ihr könnt mir da helfen.

Ich schätze der Algorithmus ist jeden bekannt (wurde im Forum immerhin schon oftmals durch exzersiert), daher werde ich den Code mal nicht posten. Sollte er doch notwendig sein werde ich dies natürlich nachreichen.

 

[bygones]

nicht int nehmen ?

long oder BigInteger oder so sollten helfen ?!

 

[Psynox]

Ja stimmt daran habe ich nicht gedacht aber es funktioniert trotzdem nicht. Das Problem ist und bleibt das gleiche. Ich poste mal doch den Code

public static void sieb_des_eratosthenes (int N) {
boolean[] gestrichen = new boolean[N+1];
		for (int i=2; i<=N; i++) {
			if (gestrichen[i] == false) { //Vielfache, der nächsthöheren nicht gestrichenen Zahl wird gestrichen
				System.out.print(i + " ");
				int j = (i*i); //Vielfache von i als Startwert
				int k = i;
				while (j < N) {	//Vielfache j=(i*k) werden gestrichen
					gestrichen[j] = true;
					k++;
					j=(i*k);
				}
			}
		}
}

Ich kann doch ein Array initialisieren, doch der Wert mit den zu initialisierenden Keys ist ein int Wert (new boolean[int]) also bin ich beim gleichen Problem wie davor auch.

Zu bemerken wäre noch ich keine Arraylisten oder ähnliches verwenden darf dabei.

 

[SlaterB]

die kürzeste Korrektur ist sicherlich
[c]while (j> 0 && j < N)[/c]
so umgehst du Zahlen mit Überlauf, in dem hohen Bereich brauchst du sie sowieso nicht,

effizienter und unabhängig vom Überlauf wäre, am Anfang die Wurzel von N zu berechnen und für alle i > dieser wurzel gar nicht erst j auszurechnen,

da du ansonsten nur bei unter 100.000 arbeitest, reicht int, größer ist dein Array eh nicht

edit:
@bone2:
das hatte ich vorher auch ungefähr so
mit
[c]long j = 1l * i * i;[/c]

edit2:
nur der Test auf > 0 könnte auf lange Sicht zu wenig sein, durch den Überlauf werden die Quadrate nicht nur negativ, sondern irgendwann auch wieder positiv:
65537 * 65537 = 131073
nicht dass deswegen eine falsche Zahl gestrichen wird..

 

[bone2]

    public static void sieb_des_eratosthenes (int N) {
        boolean[] gestrichen = new boolean[N+1];
        for (int i=2; i<=N; i++) {
            if (gestrichen[i] == false) { //Vielfache, der nächsthöheren nicht gestrichenen Zahl wird gestrichen
                System.out.print(i + " ");
                long j = ((long)i*(long)i); //Vielfache von i als Startwert
                System.out.println(j);
                int k = i;
                while (j < N) { //Vielfache j=(i*k) werden gestrichen
                    gestrichen[(int)j] = true;
                    k++;
                    j=(i*k);
                }
            }
        }
    }

so gehts

edit: hm das von SlaterB is einfacher^^
warum gibt das eig beim cast keine exception, er geht dann doch auch ins negative beim rückcast auf int

 

[Psynox]

bone2 danke genau so funktionierts, hatte an die Möglichkeit mit long und so gar nicht gedacht und dann als es erwähnt wurde hatte ich es falsch implementiert aber deine Lösung funktioniert für die Problemzahl

Ich danke herzlichst und auch allen anderen für die schnelle Beantwortung und das finden einer Lösung für mein Problem.

Grüße
David

Edit: @ SlaterB ja: auch dir Danke dein Lösungsansatz ist gut aber wie du schon sagtest irgendwann wird es wieder positiv und wieder negativ und wieder positiv usw. :-D

 

[bone2]

warum gibt das eig beim rückcast keine exception, er geht dann doch auch ins negative beim rückcast auf int

kann mir das noch jemand erklären?^^ bin gerade selber verwirrt das es funktioniert

 

[SlaterB]

was für ein Rückcast? wenn j > 65000 ist, dann verhindert die while-Schleife jegliche Verwendung,

damit j als long selber überläuft muss N schon deutlich größer werden und dann das Programm eine Weile laufen

------

> k++;
> j=(i*k);

->

j+=i;
k kann weg

 

[bone2]

wald bäume und so
wusst schonwieder nich mehr warum ich überhaupt long genommen hab


es schützt sich ja dann selber, da N ein int ist, kann J nie mehr so groß werden, das es beim cast
negativ ist

man könnte in der letzte zeile noch j = (long) i * k machen, nur zur sicherheit^^