# Primzahlen Berechnung optimieren



## Bodo1981 (17. Nov 2006)

Hallo,

hab ein Programm geschrieben, das die Primzahlen von 1 bis zu einem vom Benutzer eingegebenen Höchstwert berechnet und ausgibt. Dabei wird die Zeit gemessen. Im Moment braucht das Programm auf meinem Rechner für die Primzahlen von 1-100.000 ca. 2,5s. Nun lautet meine Frage, ob ich an meinem Programm noch irgendwas optimieren kann, damit die Berechnung noch schneller läuft.

PS: Bin auch offen für einen anderen Berechnungs-Algorithmus

Hier mein Programm:


```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Primzahlen {
	
	public static void main(String[] args) {
		boolean isprim;
		int input = 0;
		int counter = 0;
		double timebefore;
		double timeafter;
		
		try{
			BufferedReader keyboard = new BufferedReader (new InputStreamReader(System.in));
			
			System.out.println ("*********************************************************************************");
			System.out.println ("** Berechnung der Primzahlen bis zu einem vom Benutzer eingegebenen Höchstwert **");
			System.out.println ("*********************************************************************************\n\n");
			System.out.print ("Geben Sie den Höchstwert ein: ");
			
			try{
				input = Integer.parseInt(keyboard.readLine());
			} catch (NumberFormatException nfe){
				System.out.println("Keine gültige Eingabe");
			}
		} catch (IOException ioe){
			System.out.println("Keine gültige Eingabe");
		}
		
		timebefore = System.currentTimeMillis();
		
		for (int n = 2; n <= input; n++) {
			isprim = true;
			
			for (int i = 2; i < (n / 2); i++) {
				
				if (i == 2 || (i % 2) != 0 ){
					if ((n % i) == 0) {
						isprim = false;
	                    break;   
	                }
				}
			}
      
			if (isprim) {
				System.out.println(n);
				counter++;
			}
		}
		
		timeafter = System.currentTimeMillis();
		
		System.out.println ("Es gibt " + counter + " Primzahlen von 1 - " + input);
		System.out.println ("\nBenötigte Zeit(in s): " + ((timeafter - timebefore)) / 1000);
	}
}
```

Danke euch schonmal im voraus


----------



## Wildcard (17. Nov 2006)

http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes


----------



## Bodo1981 (17. Nov 2006)

Merci, hab den Algorithmus jetzt mal umgesetzt und der ist ja echt der Wahnsinn, jetzt bräuchte ich nur noch eine Bestätigung ob die Primzahlen auch wirklich stimmen. Dazu lasse ich die Primzahlen einfach zählen:

Primzahlen von 1-10.000:     1.229
Primzahlen von 1-100.000:   9.592

Kann mir bitte jemand die Zahlen bestätigen?

Hier nochmal der Algorithmus:


```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Primzahlen2 {
	
	public static void main(String[] args) {
		int input = 0;
		int counter = 0;
		double timebefore;
		double timeafter;
		
		try{
			BufferedReader keyboard = new BufferedReader (new InputStreamReader(System.in));
			
			System.out.println ("*********************************************************************************");
			System.out.println ("** Berechnung der Primzahlen bis zu einem vom Benutzer eingegebenen Höchstwert **");
			System.out.println ("*********************************************************************************\n\n");
			System.out.print ("Geben Sie den Höchstwert ein: ");
			
			try{
				input = Integer.parseInt(keyboard.readLine());
			} catch (NumberFormatException nfe){
				System.out.println("Keine gültige Eingabe");
			}
		} catch (IOException ioe){
			System.out.println("Keine gültige Eingabe");
		}
		
		boolean[] gestrichen = new boolean[input + 1];
		
		timebefore = System.currentTimeMillis();
		
		
		// Speichern aller Zahlen von 2 bis n in der ArrayList<Integer> gestrichen
		for (int n = 2; n <= input; n++) {
			gestrichen[n] = false;
		}
		
		int i = 2;
		
		while ((i * i) <= input){
			if (gestrichen[i] == false){
				for (int j = (i * i); j <= input; j = j + i){
					gestrichen[j] = true;
				}
			}
			i++;
		}
		
		for (int a = 2; a <= input; a++){
			if (gestrichen[a] == false){
				System.out.println(a);
				counter++;
			}
		}
		
		timeafter = System.currentTimeMillis();
		
		System.out.println ("Es gibt " + counter + " Primzahlen von 1 - " + input);
		System.out.println ("\nBenötigte Zeit(in s): " + ((timeafter - timebefore)) / 1000);
	}
}
```


----------



## Wildcard (17. Nov 2006)

Sieht korrekt aus  :wink:


----------



## Gast (12. Apr 2007)

der obere algorithmus gibt falsche zahlen aus die keine primzahlen sind


----------



## The_S (13. Apr 2007)

Also ich hab nen anderen Algorithmus drüber laufen lassen und komme zu den selben Ergebnissen!

Zu dem Algo: Er ist natürlich sehr schnell, auf der anderen Seite bekommt er recht schnell Speicherplatzprobleme, sobald mal eine größere Menge an Primzahlen berechnet werden soll.


----------



## Marco13 (13. Apr 2007)

.... und die Bekommt man auch dann noch, wenn man (wie es sinnvoller wäre) den "gestrichen"-Array nur 
Math.sqrt(eingabe)+1
groß macht....


----------



## Tobias (13. Apr 2007)

Da kann man ja dann weitermachen mit http://de.wikipedia.org/wiki/Sieb_des_Atkin ...

mpG
Tobias


----------

