Sieb des Eratosthenes

[sterntv]

Hallo, zusammen vielleicht kann mir einer von Euch helfen. Hier die Aufgabenstellung.

Schreiben Sie ein möglichst effizientes Java-Programm, welches zwei Zahlen vom
Typ int als untere und obere Grenzen einliest und alle Primzahlen, die zwischen
diesen liegen, ausgibt. Erzwingen Sie für die Obergrenze die Eingabe einer Zahl, die
größer ist als die Untergrenze.

hier mal mein erstes Ansatz:

import AlgoTools.IO;

/**
 * Sieb des Eratosthenes zur Ermittlung von Primzahlen. Idee: Streiche alle
 * Vielfachen von bereits als prim erkannten Zahlen.
 */

public class Sieb {

public static void main(String[] argv) {
		
	boolean[] prim;
	int j,i,u_grenze, o_grenze;
		
		
		
	IO.println("Gesucht werden Primzahlen zwischen 2000000000 und 2000010000");
		
	do{
	u_grenze=IO.readInt("Geben Sie eine untere Grenze an : " );
	}while(u_grenze<2);
		
	o_grenze=IO.readInt("Geben Sie eine obere Grenze an  : " );
	prim = new boolean[o_grenze];
		
		
		
	for(i=u_grenze; i<o_grenze+)	                                //alle Zahlen sind Primzahlen
	     prim[i] = true;
			
	     for (i=2; i<o_grenze; i++){			
                        if (prim[i])  			                                // falls i als Primzahl erkannt,
	        IO.println(i,5); 		                               // gib sie aus, und
	        for (j = i*i; 0<j && j < o_grenze; j = j+i)  	// fuer alle Vielfachen j von i
	             prim[j] = false; 				// streiche j aus der Liste
	   }
		
}
}

Frage, wieso funktioniert das Programm nicht, wenn die Zahlen zwischen 2Milliarden und 2Milliarden 1000 liegen.

 

[SlaterB]

public class Test
{
    public static void main(String[] args)
    {
        int i = 2000000000;
        System.out.println(i);
        System.out.println("das Quadrat davon: ");
        System.out.println(i * i);

        System.out.println(Integer.MAX_VALUE);
    }
}

 

[chalkbag]

Ich bezweifel, das dieses Programm überhaupt funktioniert.


Die erste Schleife soll wohl nicht nur Zeile 29 sondern auch die Schleife darunter ausführen.
Auch ist die Schleifenbedingung nach meiner Meinung eher eine Endlosschleife

   for(i=u_grenze; i<o_grenze+)

eher zu

   for(i=u_grenze; i<o_grenze; i++) 
{...}

aber eigentlich sollte das der compiler schon annörgeln, oder ist das eine neue Form der For-Schleife, welche ich noch nicht kenne?

 

[nrg]

würde nie das array von 0 bis obergrenze intialisieren sondern nur von untergrenze bis obergrenze. dann musst du dir die untergrenze als offset merken und dann ist eben index+offset deine zahl

 

[Firephoenix]

Hi,
ich glaube slater will auf long hinaus

Im Wiki findet man übrigens einen guten Pseudocode-Ansatz:
Sieb des Eratosthenes ? Wikipedia

Und dem Lehrer der diese komische IO-Klasse vergibt könnte ruhig mal jemand erklären, dass es nicht schwer ist java-lernenden mal kurz zu erklären wie sie ne gui aus 2 buttons und ner textarea zusammenklicken, damit arbeitet es sich nämlich wesentlich schöner

Für die Liste könnte man z.b. eine LikedList<Integer> nehmen, die sollte dann ja schon passende Methoden nehmen um gezielt Zahlen zu entfernen (remove), oder um das erste Element auszulesen (get(0)) etc.

Der Rest sind dann eigentlich nur noch Listenoperationen die den Pseudocode umsetzen.
Gruß

 

[sterntv]

Ich bezweifel, das dieses Programm überhaupt funktioniert.


Du hast natürlich recht, ich muss es wohl beim reinkopieren, gelöscht haben!