Hilfe bei Sieb des Eratosthenes

tatra-bennl · 23. Nov 2014

Hallo liebe Foren-Mitglieder,

im Rahmen meines Studiums belege ich an der Uni den Kurs "Grundlagen der Programmierung" (mit Java). Ich bräuchte nun Hilfe bei der folgenden Aufgabe:

"Mit dem Sieb des Eratosthenes kann für alle Zahlen von 2 bis zu einer Grenze M bestimmt werden, ob es sich um Primzahlen handelt.
Schreiben Sie ein Programm, das über das Sieb des Eratosthenes die ersten N Primzahlen ausgibt, wobei N Ihrem Programm als Kommandozeilenparameter übergeben werden soll.
Da nun eine beim Programmieren noch nicht bekannte Anzahl von Primzahlen gesucht wird, kann es sein, dass eine gewählte Grenze M für das Sieb nicht ausreicht. In diesem Fall soll die Grenze erhöht und die gesamte Berechnung erneut durchgeführt werden. Starten Sie z.B. mit einer Grenze M für das Sieb von 9 und erhöhen Sie die Grenze nach jedem Durchlauf um Faktor 10."

Ich habe dazu schon den folgenden Ansatz:

Java:

import java.util.Scanner;

public class Sieb {

	public static void main(String[] args) {
		
		int M = 1;					//Variable M (1.Primzahl bis M-te Primzahl)
		int N;
		Scanner eingabe = new Scanner(System.in);
		N = Integer.valueOf(eingabe.next());
		boolean[] p = new boolean[M];				
		
		for (int i=2; i<M; i++)						
			p[i] = true;									
		
		for (int i=2; i*i<M; i++) { 				
			if (p[i]) {								
				for (int n=2; n*i<M; n++)			
				    p[n*i] = false;	
                //wenn n*i<M, dann setze Boolschen Wert auf "false" (d.h. Vielfache von i nicht prim)
			}
		}
		
		for (int i=2; i<M; i++)
			   if (p[i])
                           System.out.println(i);							
	}
}

Hier komme ich nun nicht weiter. Mein Problem ist, dass ich keine Idee habe für einen Algorithmus, d.h. ich weiß nicht, wie ich dem Programm begreiflich mache, dass ich die ersten N Primzahlen haben möchte (und nicht die Primzahlen bis zu einer bestimmten Grenze).
Habt ihr eine Idee bzw. könnt mir einen Gedankenanstoß geben erstmal für einen Algorithmus (in deutscher Sprache)? Danach würde ich dann versuchen, diesen in Java umzuschreiben.

Ich bin für Eure Hilfe dankbar und freue mich auf Antworten

soong · 23. Nov 2014

Mein Freund, ich glaube wit kommen sogar von der selben UNI :lol:
Also ich habe so einen Ansatz:

Java:

class Sieb
{
	public static void main(String args[]){
		int n = Integer.parseInt(args[0]);
		int status = 1;
		int num = 3;

		if (n >= 1){	
         System.out.println(2);
		}
		
		for ( int i = 2 ; i <=n ;){
         
			for ( int j = 2 ; j <= Math.sqrt(num); j++){

				if ( num % j == 0){
					status = 0;
					break;
				}
			}         
			
			if ( status != 0){
				System.out.println(num);
				i++;
			}
         
		 status = 1;
         num++;
      }         
   }
}

chuxXo · 24. Nov 2014

tatra-bennl hat gesagt.:
Hier komme ich nun nicht weiter. Mein Problem ist, dass ich keine Idee habe für einen Algorithmus, d.h. ich weiß nicht, wie ich dem Programm begreiflich mache, dass ich die ersten N Primzahlen haben möchte (und nicht die Primzahlen bis zu einer bestimmten Grenze)

Hallo tetra,

mit einer while-Schleife könntest du dein Programm doch so lange rennen lassen, bis dein Zähler für Primzahlen die 10 erreicht hat

Die Zahl, die auf eine Primzahl kontrolliert wird, wird dabei immer nach jedem Durchlauf um 1 erhöht.

chuxXo · 24. Nov 2014

Hallo soong,
Hab mir deinen Code gerade mal angeschaut und hab ein paar Fragen :

soong hat gesagt.:
Java:

if (n >= 1) { System.out.println(2); }

Was machst du denn in dieser Zeile ?

Immer wenn die Eingabe größer oder gleich 1 ist wird eine "2" ausgegeben.
Was wenn die Eingabe 11 ist ? Dann wird ebenfalls eine "2" ausgegeben.

soong hat gesagt.:
Java:

if ( status != 0)

Nimm doch anstatt einer int für status ein boolean und setz dieses entsprechend auf true oder false.

soong hat gesagt.:
Java:

for ( int j = 2 ; j <= Math.sqrt(num); j++)

Ich bin der Meinung, dass du diese Zeile komplett weglassen kannst

tatra-bennl · 24. Nov 2014

Hallo chuxXo,

aber ich soll doch die ersten N Primzahlen ausgeben lassen. Das Programm wählt sich dann eine Grenze. Wenn ich z.B. N=10 eingebe (also die ersten 10 Primzahlen haben will), kann es ja passieren, dass die vom Programm gewählte Grenze zu klein ist -> dann soll es die Grenze ver-10-fachen. Warum um 1 erhöhen? Oder habe ich einen Denkfehler?...

tatra-bennl · 24. Nov 2014

soong hat gesagt.:
Code:

if (n >= 1){ System.out.println(2); } }

Ich verstehe die Zeile so, dass im Fall N>1 auf jeden Fall erstmal die 2 ausgegeben wird, d.h. die 2 wird immer ausgegeben. Müsste doch stimmen, oder?

und @soong: Ja, wir kommen von derselben Uni

chuxXo · 25. Nov 2014

tatra-bennl hat gesagt.:
Hallo chuxXo,

aber ich soll doch die ersten N Primzahlen ausgeben lassen. Das Programm wählt sich dann eine Grenze. Wenn ich z.B. N=10 eingebe (also die ersten 10 Primzahlen haben will), kann es ja passieren, dass die vom Programm gewählte Grenze zu klein ist -> dann soll es die Grenze ver-10-fachen. Warum um 1 erhöhen? Oder habe ich einen Denkfehler?...

Das ist ja nicht all zu schwer

Sobald eine Primzahl gefunden wurde, erhöhst du den Zähler der Primzahlen um 1

Ich hab keine Ahnung, was du vervielfachen willst.... Also ich hab ein kleines, sehr einfaches Programm geschrieben, welchem du mitteilst, ab welcher Zahl x du die nächsten y Primzahlen haben willst.

Hast du deinen Code schon verändert ? Sonst können wir ja auf diesem aufbauen

chuxXo · 25. Nov 2014

tatra-bennl hat gesagt.:
Ich verstehe die Zeile so, dass im Fall N>1 auf jeden Fall erstmal die 2 ausgegeben wird, d.h. die 2 wird immer ausgegeben. Müsste doch stimmen, oder?

Warum willst du immer eine 2 ausgeben lassen ?

Du hast eine 10 und eine 2 wird ausgegeben

tatra-bennl · 25. Nov 2014

chuxXo hat gesagt.:
Das ist ja nicht all zu schwer Sobald eine Primzahl gefunden wurde, erhöhst du den Zähler der Primzahlen um 1
Ich hab keine Ahnung, was du vervielfachen willst....

Das steht in der Aufgabe so vorgeschrieben. Dem Programm soll die Zahl N als Kommandozeilenparameter übergeben werden. Dann wählt sich das Programm eine Grenze, führt den Algorithmus "Sieb" durch. Dann kann es passieren, dass die vom Programm gewählte Grenze zu klein ist. Das Programm soll diese dann verzehnfachen und den Algorithmus mit der neuen Grenze erneut durchführen. Steht so in der Aufgabe...

chuxXo hat gesagt.:
Warum willst du immer eine 2 ausgeben lassen ?

Weil die 2 die erste Primzahl ist. Es sollen immer alle Primzahlen von der ersten bis zur N-ten Primzahl ausgegeben werden. Somit muss die 2 für alle Werte von N (> 1) ausgegeben werden.

z.B.
N=1 -> Programm gibt "2" aus
N=2 -> Programm gibt "2" und "3" aus
N=5 -> Programm gibt "2", "3", "5", "7", "11" aus
also die "2" wird in jedem Fall immer ausgegeben

chuxXo hat gesagt.:
Hast du deinen Code schon verändert ?

Nein, habe ich leider noch nicht, weil ich immer noch nicht weiß, wie...

Leider habe ich wirklich keinen Schimmer bzgl. des Algorithmus...

chuxXo · 25. Nov 2014

Also...

Das ganze kann man weglassen. Wenn du folgendes hast:

Java:

if (n >= 1) {	
     System.out.println(2);
}

Dann wird die 2 ausgegeben, da sie eine Primzahl ist. Würdest du dann weiter so verfahren ? :

Java:

if (n == 3){	
     System.out.println(3);
}

Klar, du darfst dir gerne jede Primzahl mit "if" überprüfen, aber das wird nicht der Sinn und Zweck sein.

Also fangen wir von vorne an. Folgende Methode gibt dir zurück, ob die übergebene zahl eine Primzahl ist:

Java:

private static boolean isPrim(long prim) {		
     if (prim <= 2) 
           return true;
		
     for (int j = 2; j < prim; j++) {
          if ((prim % j) == 0) {
		return false;
	  }
     }
     return true;
}

Probier die mal aus und erklär mir, wie diese funktioniert. Dann schauen wir danach, wie wir es berwerkstelligen können, dass er dir immer x primzahlen ausgibt

tatra-bennl · 25. Nov 2014

Ich wollte das nicht bei jeder Zahl überprüfen. Ich wollte nur verallgemeinern, dass die "2" ja auf jeden Fall immer mit dabei ist. Nur bei der 2 wollte ich das so machen. Aber egal, das ist ja anscheinend nicht notwendig...

Deinen Code verstehe ich glaube ich so weit, aber müsste in Zeile 3 nicht if (prim >=2) stehen?

Flown · 26. Nov 2014

Wenn du if(prim >= 2) schreiben würdest, dann wäre jede Zahl größer gleich 2 eine Primzahl!

Aber in eurer Aufgabe geht es ja eigentlich nicht um die Prüfung auf Primzahlen, sondern um das Sieb des Eratosthenes zu programmieren. Auf Wikipedia ist der Algorithmus zu finden, der dann nur noch "abgetippt" werden muss.

chuxXo · 26. Nov 2014

Ok, stimmt. Dann lag ich wohl Falsch. Ist echt sehr gut veranschaulicht auf Wikipedia.

tatra-bennl · 26. Nov 2014

Flown hat gesagt.:
Aber in eurer Aufgabe geht es ja eigentlich nicht um die Prüfung auf Primzahlen, sondern um das Sieb des Eratosthenes zu programmieren. Auf Wikipedia ist der Algorithmus zu finden, der dann nur noch "abgetippt" werden muss.

Nein, der Algorithmus auf Wikipedia ist nicht der richtige für diese Aufgabe. Dort wird das Sieb beschrieben, das mir alle Primzahlen von 2 bis zu einer bestimmten Grenze angibt.

Meine Aufgabe besteht aber darin, DIE ERSTEN N PRIMZAHLEN anzugeben.

Wikipedia: z.B. alle Primzahlen bis 10: also 2, 3, 5, 7
Meine Aufgabe: z.B. die ersten 10 Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Es reicht also nicht, den Wikipedia-Algorithmus abzutippen...

Ich merke, dass die Aufgabe nicht nur mir Probleme zu bereiten scheint...

Flown · 26. Nov 2014

tatra-bennl hat gesagt.:
"Mit dem Sieb des Eratosthenes kann für alle Zahlen von 2 bis zu einer Grenze M bestimmt werden, ob es sich um Primzahlen handelt.
Schreiben Sie ein Programm, das über das Sieb des Eratosthenes die ersten N Primzahlen ausgibt, wobei N Ihrem Programm als Kommandozeilenparameter übergeben werden soll.
Da nun eine beim Programmieren noch nicht bekannte Anzahl von Primzahlen gesucht wird, kann es sein, dass eine gewählte Grenze M für das Sieb nicht ausreicht. In diesem Fall soll die Grenze erhöht und die gesamte Berechnung erneut durchgeführt werden. Starten Sie z.B. mit einer Grenze M für das Sieb von 9 und erhöhen Sie die Grenze nach jedem Durchlauf um Faktor 10."

Les dir deine eigene Angabe durch und dann reden wir weiter!

Mein Rat an dich: Implementiere doch mal das Sieb und dann helf ich dir weiter!

chuxXo · 26. Nov 2014

tatra-bennl hat gesagt.:
Meine Aufgabe besteht aber darin, DIE ERSTEN N PRIMZAHLEN anzugeben.

Wikipedia: z.B. alle Primzahlen bis 10: also 2, 3, 5, 7

Jetzt bist du verwirrt

Deine beschriebene Grenze N wo in deiner Aufgabenstellung die 9 sein soll, ist eben in Wikipedia die 10.

tatra-bennl · 26. Nov 2014

Flown hat gesagt.:
Les dir deine eigene Angabe durch und dann reden wir weiter!

Ich habe mir meine Aufgabe schon durchgelesen. Da steht Schreiben Sie ein Programm, das über das Sieb des Eratosthenes die ersten N Primzahlen ausgibt

DIE ERSTEN N Primzahlen. Nicht die Primzahlen bis zu einer von mir gewählten Grenze. Die Grenze wählt sich das Programm selbst.

Ich habe mir überlegt, dass man ja eine for-schleife einfügen könnte:

Java:

 for (M=1; .......; M*10)
  //Führe Algorithmus "Sieb" aus

Außerdem habe ich mir überlegt: ich gebe ja dem Programm die von mir gewünschte Anzahl von Primzahlen an (N). Das Programm beginnt mit einer Grenze M. Wenn diese zu klein ist, verzehnfacht es die Grenze (siehe for-Schleife). Nun kann es ja sein, dass diese Grenze wiederum zu groß ist; d.h. das Programm soll ja nur N Primzahlen angeben, nicht aber alle bis zur Grenze.
Ich würde also am Ende einfügen:

Java:

 System.out.Println(....) //Primzahl ausgeben

wobei das Programm nach der N-ten Zeile stoppen soll. Ginge das so oder so ähnlich?

tsaaa3 · 26. Nov 2014

Hallo!
nachdem ich mir das jetzt redlich überlegt hab, finde ich einfach keine gescheite Lösung... Entweder a) oder b)

a) ich denke zu kompliziert, und die Lösung ist viel einfacher!?
b) die Aufgabe ist schlecht gestellt, und irgendwie könnte man bei einer normalen Erathosthenes-Implementierung fast genausoviel lernen. Das Problem sorum anzugehen, ist nur kruxig...

Ich würd mal kurz beschreiben, wie ich mir das vorgestellt hab:
-gebe Menge 'anzahl' an Primzahlen an, die ich haben will
-Erstelle einen array der Größe 'anzahl'+1
-Fülle ihn: 0->0; 1->1;....anzahl->anzahl.

1)Darin wird ab der ersten sinnvollen Möglichkeit "gesiebt". //VL-Implementierung
(1.1)Dabei wird nicht mehr zwischen T/F entschieden, sondern es steht entweder eine Zahl drin, oder eine 0.)
3)Jetzt werden alle nicht-0 im array linksbündig geschoben, bis rechts nur noch 0en stehen.
4)Alle 0en werden ersetzt mit Zahlen, die wir noch nicht hatten.
(4.1)Wir hängen also ein neues Stück Zahlenstrang an, was direkt den letzten Abbruch ergänzt. )
-5-fangen wieder mit 1 an.

-6-jetzt hat man einen 'anzahl'+1_langen array, der 'anzahl' viele Primzahlen enthält. (Was 0 für eine Zahl ist, das überlasse ich den Mathematikern^^)
Den kann man jetzt ausdrucken.
Mein Programm läuft, hat aber z.B. mit n=20 Primzahlen schon eine Laufzeit von 1 Minute wegen der vielen for-schleifen...insbesondere wird das Auffüllen und Sieben natürlich ineffizienter, je voller der array ist.

soong · 26. Nov 2014

wärst du so gnädig und zeigst uns deinen ansatz?

Flown · 27. Nov 2014

Also ihr seid im falschen Studium. Die Aufgabenstellung ist eindeutig!

1. Sieb programmieren
2. printNPrimes programmieren

Das sind mal die Schritte die ich auch oben beschrieben habe!

Das Sieb nimmt den Parameter M entgegen, dass heißt aber nicht das ihr auch M Primzahlen rausbekommt!!!
Ihr liefert mit dem Sieb die Primzahlen bis zu Grenze M zurück, überprüft ob ihr genügend Primzahlen gesammelt habt, damit ihr sie ausgeben könnt. Wenn nein, dann lässt ihr das Sieb mit M*10 nochmals laufen!

Wenn ihr dann genügend Primzahlen gesammelt habt, gebt ihr einfach die gewünschten n Primzahlen aus!

Dauer der Aufgabe 5 min!

soong · 27. Nov 2014

Java:

import java.util.*;

public class Sieb{

	public static void main (String []args){
	
		int max = Integer.parseInt(args[0]);
		
		boolean []istPrim = new boolean [max];
	    
		for (int i=2; i<istPrim.length;i++) {
			istPrim[i]=true;
		}
		
		for (int i=2; i<istPrim.length;i++) {
		
			for (int j=2;i*j<istPrim.length;j++) {
				istPrim[i*j]=false;
			}
		}
		
		for(int i=2;i<istPrim.length;i++) {
			if(istPrim[i]) {
				//System.out.println(istPrim[i]); // true und false Ausgabe
				System.out.println(i); // Ausgabe der Primzahlen				
			}
		}
   }
}

Erste Teilaufgabe erledigt, Sieb programmiert.

Flown · 27. Nov 2014

Jetzt musst du nur noch die Primzahlen sammeln und in ein array werfen. Über das boolean array iterieren und an der i-ten Stelle das true ist in das eben genannte Array werfen.

tatra-bennl · 27. Nov 2014

@Flown:
Erstmal danke für deine Hilfe! Jedoch finde ich es leicht wagemutig von dir zu beurteilen, ob mein Studium das richtige für mich ist...

Programmierung ist einfach nicht so meine Stärke wie es scheint.

Zu deinem Lösungsansatz:
Könntest du das evtl. in einem Code zeigen? Ich komme einfach nicht weiter; sitze seit Montag dran.

Meine Idee war ja, die Nummer der ausgegeben Zeilen als Variable zu definieren und dann eine if-Anweisung einzufügen:
if (Zeilennummer == N)
break;

Vielleicht ist das aber zu kompliziert...?

Flown · 27. Nov 2014

Das war ein wenig zu hart gesagt, denn jeder soll selbst entscheiden, was er studieren will. Doch wer meine Vorschläge/Hilfestellungen als Blödsinn abtut und sich nicht helfen lassen will, legt mir soetwas nahe.

Ich hab die Aufgabe an dem Tag gelöst, an dem du diesen Thread geöffnet hast!

Java:

import java.util.Arrays;

public class EratostheneSieve {
  public static void main(String... args) {
    EratostheneSieve sieve = new EratostheneSieve();
    sieve.printNPrimes(100);
  }
  
  private int m = 9;
  private static final int FACTOR = 10;
  private int[] primes;
  
  public void printNPrimes(int n) {
    if (primes == null) {
      primes = sieve(m);
    }
    while (primes.length < n) {
      m *= FACTOR;
      primes = sieve(m);
    }
    System.out.print("[");
    for (int i = 0; i < n; i++) {
      if (i != 0) {
        System.out.print(", ");
      }
      System.out.print(primes[i]);
    }
    System.out.println("]");
  }
  
  private int[] sieve(int n) {
    int[] prime = new int[n];
    int nrOfPrimes = 0;
    boolean[] isNotPrime = new boolean[n];
    int i;
    for (i = 2; i * i < n; i++) {
      if (!isNotPrime[i]) {
        prime[nrOfPrimes++] = i;
      }
      for (int j = i * i; j < n; j += i) {
        isNotPrime[j] = true;
      }
    }
    for (i++; i < n; i++) {
      if (!isNotPrime[i]) {
        prime[nrOfPrimes++] = i;
      }
    }
    
    return Arrays.copyOf(prime, nrOfPrimes);
  }
}

soong · 27. Nov 2014

Danke, trotzdem...

tatra-bennl · 27. Nov 2014

Du hast die Aufgabe gleich lösen können, ich eben nicht; man kann ja nicht alles können.

Dankeschön für den Code, wenn ich zu Hause bin, schau ich mir das noch mal genau an.

Deine Lösungsansätze habe ich übrigens keineswegs als Blödsinn abgetan. Wenn das so angekommen ist, tut mir das wirklich Leid. Wahrscheinlich haben wir uns (bzw. ich dich) einfach missverstanden.
Ich wollte eigentlich nur meine Gedanken, die ich zu der Aufgabe hatte, hier mit Java-erfahrenen Leuten (wie wahrscheinlich dir) diskutieren und Probleme klären.

Ich lasse mir gern helfen, sonst hätte ich den Thread nicht eröffnet.

Hilfe bei Sieb des Eratosthenes

Mitglied

Mitglied

Bekanntes Mitglied

Bekanntes Mitglied

Mitglied

Mitglied

Bekanntes Mitglied

Bekanntes Mitglied

Mitglied

Bekanntes Mitglied

Mitglied

Administrator

Bekanntes Mitglied

Mitglied

Administrator

Bekanntes Mitglied

Mitglied

Neues Mitglied

Mitglied

Administrator

Mitglied

Administrator

Mitglied

Administrator

Mitglied

Mitglied