# Primzahlen bis 1000000



## Anfänger22 (2. Nov 2010)

Ich bin ein Anfänger und möchte mich weiterbilden...leider komm ich bei dieser aufgabe nicht vorbei...
wäre jemand so nett, mir die Aufgabe so leicht wie möglich zu schreiben...will des einfach mal verstehen...selber komme ich nicht mehr weiter


Schreiben Sie ein Programm, das alle Primzahlen bis 1 000 000 berechnet. 
Das Programm soll leicht auf andere Höchstzahlen änderbar sein.
Sieb des Eratosthenes:
Zuerst alle geraden Zahlen (bis auf 2) streichen, dann alle Vielfachen von 3, usw. mit der jeweils nächsten Primzahl.
überlegen Sie sich, mit welcher Zahl maximal gestrichen werden muss. 
Anmerkung: Man könnte das auch mit Nicht-Primzahlen machen (z.B. 4), dann streicht man aber nur Zahlen,
die vorher schon gestrichen worden sind. 

Geben Sie zur Kontrolle die ersten 100 und die letzten 10 Primzahlen aus, immer 10 pro Zeile.


----------



## bygones (2. Nov 2010)

suchen ist schon schwierig...

allein bei google findet man zig einträge nur in diesem Forum dazu. Wenn du schon was hingekautes bekommen willst dann ists einfacher google zu nutzen.

die moralische Keule von wegen "weiterbilden" und dann nach fertigem zu fragen erspar ich mir....


----------



## Andi_CH (2. Nov 2010)

Im Gegensatz zur Lottoziehung sind hier die Requirements SEHR präzise beschrieben - da ist ja sogar das Design schon gelöst.

Überlegung: 10^6 hat locker in einem int platz

Offene Frage - "überlegen Sie sich, mit welcher Zahl maximal gestrichen werden muss. " ist eine mathematische und hat nichts mit Java zu tun - du musst bis zur Wurzel des Primzahlenkandiaten streichen. (Falls du es wissen willst erkläre ich dir warum, aber kannst es auch einfach glauben.)

Die "Anmerkung" kannst du einfach vergessen - die bringt nichts.

So, wenn ich jetzt die Lösung auch nur ansatzweise hier reinkopiere hast du nichts gelernt.

(Übrigens: Programmieren beginnt immer auf einem "Papier" - ok, es kann auch ein office oder sonst was Dokument sein, aber den Kompiler braucht man erst später)


----------



## ARadauer (2. Nov 2010)

> mir die Aufgabe so leicht wie möglich zu schreiben


Wir machen hier keine ausaufgaben.
Wir helfen gerne und bieten Hilfestellungen, wenn der Fragende Eigeninitative zeigt...



> selber komme ich nicht mehr weiter


was hast du den bereits...


----------



## ARadauer (2. Nov 2010)

> Offene Frage - "überlegen Sie sich, mit welcher Zahl maximal gestrichen werden muss. " ist eine mathematische und hat nichts mit Java zu tun - du musst bis zur Wurzel des Primzahlenkandiaten streichen. (Falls du es wissen willst erkläre ich dir warum, aber kannst es auch einfach glauben.)


Gibts leute die da warum fragen?


----------



## Anfänger22 (2. Nov 2010)

wer will kann gerne helfen...wer nicht soll sich bitte daraushalten...das problem ist, dass ich bei dieser aufgabe nix versteh...hab mich an euch gewendet, damit ihr mir des mal erklärt. 
ich flehe euch nicht an...ich hab nur höfflich gefragt ob ihr mir dabei helfen könnt....
die aufgabe steht oben...und ich würde mich freuen, wenn mir jemand die aufgabe mal lösen würde...danke


----------



## ARadauer (2. Nov 2010)

Na was jetzt? Helfen oder lösen?
Das ist schon ein Unterschied. Beim helfen musst du auch was machen, biem Lösen poste ich nur die Lösung.

Also ich versuch mal zu helfen.
Beim Sieb des Eratosthenes geht man her und macht sich ein boolean array wo drinnen steht ob die Zahl eine Primzahl ist.

zb so


```
int anzahl = 100;		
		boolean[] isPrim = new boolean[anzahl];
		
		if(isPrim[6]){
		   System.out.println("Ja ist ein Primzahl");
		}
```
wie der geübte mathematiker erkennen kann, fehlt her noch was... 6 ist gar keine primzahl...

also müssen wir alle nicht primzahlen streichen

alle die durch, 2 teilbar sind auf false, alle die durch 3 teilbar sind auf false, alle die durch 4 mhnn seltsam.. macht ja keinen sein, alle die durch 4 teilbar sind haben wir schon gestrichen... die warn ja schon durch 2 teilbar... mhn also wir nehmen nur 2, 3 und alle weiteren primzahlen. so das it der ansatz... 

so wie setzen wir jetzt alle die druch 2,3, usw teilbar sind auf false... wir teilen nichit sondern setzen alle vielfachen auf false...


```
i ist hier die zahl wo wir prüfen...
for(int j = i*i;j<anzahl; j+=i)					
   isPrim[j] = false;				
}
```

so ungefähr, aussen rum noch ne for schleife die muss aber nicht die ganzen prüfen.. nur bis zur wurzel.. is so.
dann noch das if(isPrim_){ um das was ich schon gepostet habe und fertig..._


----------



## Landei (2. Nov 2010)

Man muss das array allerdings erst mal mit lauter trues initialisieren. Am einfachsten mit java.util.Array.fill


----------



## ARadauer (2. Nov 2010)

:lol: stimmt


----------



## Anfänger22 (2. Nov 2010)

ohh danke...ist das jetzt die ganze lösung??? poste bitte mal alles auf... aber bin dir echt dankbar


----------



## Anfänger22 (2. Nov 2010)

```
import java.io.*;

public class Primzahl {
  
  public static void main(String[] args) throws IOException {
    // bestimmt Primeigenschaft
    
    BufferedReader in = new BufferedReader(
                          new InputStreamReader(System.in));
    
    // Zahl erfragen
    String s;    // String für eingegebene Zeile
    System.out.println("Positive ganze Zahl eingeben:");
    s = in.readLine();
    int zahl = Integer.parseInt(s);
    
    boolean isPrim = true;  // bis zum Beweis des Gegenteils
    int teiler = 1;         // gefundener Teiler
    
    if (zahl % 2 == 0) { // durch 2 teilbar
      isPrim = false;
      teiler = 2;
    } else {
      int max = (int) Math.floor(Math.sqrt((double) zahl));
      for (int i=3; i<=max; i=i+2) {
        if (zahl % i == 0) {  // durch ungerade Zahl kleiner Wurzel teilbar
          isPrim = false;
          teiler = i;
        }
      }
    }
    
    // Ausgabe des Ergebnisses
    if (isPrim) {
      System.out.println(zahl + " ist eine Primzahl");
    } else {
      System.out.println(zahl + " ist durch " + teiler + " teilbar");
    }
  }
}
```
das wär jetzt die lösung ausm buch gewesen.


----------



## Landei (2. Nov 2010)

Kleines Rätsel: Was steht im Forum rot über der Antwort-Box?


----------



## Anfänger22 (2. Nov 2010)

Landei hat gesagt.:


> Kleines Rätsel: Was steht im Forum rot über der Antwort-Box?



erledigt^^


----------



## Anfänger22 (2. Nov 2010)

Anfänger22 hat gesagt.:


> ```
> import java.io.*;
> 
> public class Primzahl {
> ...



aber kann man sich das leben auch einfacher machen und die lösung leichter machen???
bitte ganzes programm schreiben


----------



## ARadauer (2. Nov 2010)

> aber kann man sich das leben auch einfacher machen und die lösung leichter machen???


ja das sieb des Eratosthenes anwenden. Warum fragst du eigentlich hier im Forum? Das ist ein Standard Beispiel, das schon von Millionen von Studenten gelöst wurde... alleine auf der ersten seite in google wenn ich nach "Eratosthenes java" suche finde ich 5 Lösungen?

naja ausnahmsweise...


```
public class Sieb {	

	public static void main(String[] args) {
		
		int anzahl = 100;		
		boolean[] isPrim = new boolean[anzahl];
		
		//init
		for(int i = 0; i < isPrim.length; i++)
			isPrim[i] = true;
		
		//primzahlen berechnen
		int i = 2;
		while(i*i<anzahl){			
			if(isPrim[i]){				
				for(int j = i*i;j<anzahl; j+=i)					
					isPrim[j] = false;				
			}
			i++;
		}		
		
		//Ausgabe
		for(int k = 2; k < isPrim.length; k++){
			if(isPrim[k])
				System.out.print(k+", ");
			if((k % 100) == 0)
			   System.out.println();
		}
	}
}
```
am Ende vom Semester verzweifelst du sowieso....


----------



## Anfänger22 (2. Nov 2010)

es ist noch kein meister vom himmel gefallen....ich übe


----------



## ARadauer (2. Nov 2010)

mhn ich versteh dich schon, das sieht alles sehr komplex aus und du denkst dir wenn du die lösung hast kannst du dir das ja anahnd des fertigen codes beibringen... aber glaubs mir.. das ist vollkommen falsch.

1. das ist ein ganz einfaches beispiel, das man schon mit papier und bleistift nachvollziehen kann, das sieht nur komliziert aus.
2. Durch das code lesen lernt man das programmieren nicht. Eigenen Code schreiben ist viel einfacher als fremden Code verstehen und man lernt dabei viel mehr.



> es ist noch kein meister vom himmel gefallen....ich übe


dazu sind ja solche Beispiele da... aber man muss sie selber machen, damit man das Basiswissen lernt.

Im Grunde hast du dir gerade die Konjugations Hausübung in Französch kopiert. Wenn nu nächstes Semster einen Aufsatz schreiben musst hast du keine Chance...


----------

