Primzahlberechnung optimieren

[campino12]

Guten Abend zusammen,

ich studiere momentan Informatik im 1. Semester an einer FH und lerne dort als erste Programmiersprache JAVA.

Um mir das lernen zu vereinfachen, habe ich selbst ein kleines programm geschrieben, welches bei eingegebene Zahlen überprüft, ob eine Primzahl vorliegt oder nicht. Das Problem an der sache ist nur, dass das ganze bei kleine Zahlen noch recht gut funktioniert, allerdings bei großen Zahlen schon eine ganze weile benötigt wird, bis ein Ergebniss vorliegt.

Ich zeige euch am besten einfach mal den Quelltext, dass jeder weis um was es eigentlich geht:

package a.inf.prg1.test;

public class Primzahlen {

	public static void main(String[] args) {
		long zahl = 2147483647l;
		if (zahl % 2 == 0) {
			System.out
					.println(zahl + " ist KEINE Primzahl, da durch 2 teilbar");
			return;
		}
		long i = 3;
		while (i * i < zahl & zahl % i != 0) {
			System.out.println(zahl + " nicht durch " + i + " teilbar");
			i = i + 2;
		}
		if (i * i > zahl) {
			System.out.println(zahl + " ist Primzahl");
		} else {
			System.out.println(zahl + " ist KEINE Primzahl, da durch " + i
					+ " teilbar");
		}
	}
}

Über Wikipedia habe ich einen Algorithmus gefunden, welcher wahrscheinlich performanter ist, allerdings verstehe ich das nciht so ganz...

http://de.wikipedia.org/wiki/Miller-Rabin-Test

Dort steht beschrieben wie man eine Zahl auf die Primeigenschaft hin überprüfen kann.

Aus diesen Hinweisen ist bei mir folgender Quelltext entstanden, allerdings nicht funktionsfähig und wahrscheinlich auch nicht sehr schön programmiert:

package a.inf.prg1.test;

import java.util.Random;

public class CheckPrimnumbers {

	/**
	 * @date 2007-10-16
	 * @param args
	 * @author Alexander
	 * @description Checks if a entered number (int) is a primnumber
	 */
	public static void main(String[] args) {
		// Say Hello
		System.out.println("Check Primenumbers");
		System.out.println("-----------------------------------------------------------");
		System.out.println("Checks if a entered number is a primenumber");
		System.out.println("-----------------------------------------------------------");
		// Beginning of main programm
		int n = 5;
		int d = 1; // n - 1 = d * 2^s <== Rest not dividable through 2
		int r = 1; // 0 <= r <= s
		int s = 1; // s = max { r in N | 2^r teilt n - 1}
		// Code by Andreas Lunz Start
		int a = rand.nextInt(n) + 1;
		if (Math.pow(n, a) == 1 % n) {
			if (0 <= r && r <= s) {
				if (n - 1 == d * Math.pow(2, s)) {
					System.out.println("Your entered Number " + n
							+ "is a Primenumber.");
				}
			} else {
				System.err.println("Your entered Number " + n
						+ "is NOT a Primenumber");
			}
		}
		// Say Good Bye
		System.out.println("------------------------------------------------------------");
		System.out.println("Thank you for using this usefull small utillity!");
		System.out.println("For any problems don't hesitate to contact me!");
		System.out.println("(c) by Alexander Kiefer FH-Augsburg WS 2007 / 2008");
		System.exit(0)
	}
}

Nun zu meinen Fragen:

1. Welches von beiden Programmen ist im Endeffekt besser?
2. Wie bekomme ich das 2. Programm zum laufen bzw. was ist noch falsch?
3. Gibt es eine Möglichkeit diese Programme entsprechend Performanter zu schreiben?

Schonmal Danke
Grüße
Alexander

 

[Thomas Darimont]

Hallo,

du weist schon, dass 2 eine Primzahl ist, oder?

Gruß Tom

 

[kaMii]

Ich habe mir das ganze jetzt nicht so genau angeschaut, aber zumindest für das erste Programm könntest du etwas verbessern:

Anstatt mit der Schleife bei 3 zu beginnen, könntest du bei der schleife mit 4 beginnen und den fall für 3 dadurch absichern, das du die Quersumme der Zahl nimmst und diese durch %3 teilst. Sollte es einen Rest geben hast du eine Primzahl (sofern die restlichen Versuche mit anderen Zahlen das gleiche ergeben...)
Das ganze spart zwar nicht so viel Zeit, aber zumindest bei sehr großen Zahlen dürfte es etwas schneller gehen.

Darüber hinaus könntest du auch noch für 5 nur die letzte Stelle der Zahl abprüfen, da für einen Teiler da entweder eine "0" oder "5" stehen muss.

Gruss Ben

 

[zeja]

Wenn du die ganzen System.ou.println weglässt dürfte das auch ziemlich Zeit sparen.

 

[Anime-Otaku]

Zu Primzahlen kannst du dir auch mal http://www.primzahlen.de/ anschauen