Primzahlen Berechnung optimieren

[Bodo1981]

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]

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

 

[Bodo1981]

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]

Sieht korrekt aus :wink:

 

[Gast]

der obere algorithmus gibt falsche zahlen aus die keine primzahlen sind

 

[The_S]

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]

.... 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]

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

mpG
Tobias