Java, Primzahl berechnen.

icarus2

So, ich hab dir kurz eine einfach Methode gebastelt, die ziemlich grosse Primzahlen berechnen kann:

/**
	 * Method to determine whether a number is a prime number or not.
	 * 
	 * @param potentialPrime - number to check
	 * @return true if it is a prime number, else false
	 */
	public static boolean isPrimeNumber( final long potentialPrime ){

		// if the potentialPrime is smaller than 2, it is not a prime number
		if( potentialPrime < 2)
			return false;

		// checks first whether the number is even
		if( potentialPrime % 2 == 0 ){
			// if the potentialPrime is 2, the it is a prime number
			if( potentialPrime == 2)
				return true;
			// if even and not 2, the it is no prime number
			return false;
		}

		// Divides the potentialPrime with all odd numbers bigger than
		// 2.
		for( int i = 3; i < Math.sqrt( potentialPrime ); i += 2){
			// checks whether the remainder is 0. If so, the potentialPrime
			// is no prime number
			if( potentialPrime % i == 0)
				return false;
		}

		// If the remainder has never been 0, the potentialPrime is 
		// a prime number
		return true;

	}

Es gibt noch leistungsfähigere Algorithmen. "The sieve of Eratosthenes" wäre da z.B. eine Möglichkeit... habe ich selber irgendwo mal programmiert, finde ich aber gerade nicht mehr. Das "Sieve of Aktin" wäre noch effektiver, ist aber meines Wissens nach auch ziemlich kompliziert.

sollte man nicht zu der wurzel noch ein 0.5 dazu rechnen, so stehts zumindest auf wiki

for( int i = 3; i < Math.sqrt( potentialPrime )+0.5; i += 2){

lg javaNoob

volkard

javaNoob schrieb:

sollte man nicht zu der wurzel noch ein 0.5 dazu rechnen, so stehts zumindest auf wiki
for( int i = 3; i < Math.sqrt( potentialPrime )+0.5; i += 2){

In C++ schreiben wir kein +0.5, aber dafür nehmen wir <= statt <.

icarus2

Ja, da sollte ein <= stehen und nicht in <. Sry, ich hab den Code in 5min kurz geschrieben.

PS:
Auch in Java schreibt man <= statt < x + 0.5... das +0.5 sieht merkwürdig aus.

otze

Wie hier mal wieder Hausaufgaben gelöst werden

icarus2 schrieb:

PS:
Auch in Java schreibt man <= statt < x + 0.5... das +0.5 sieht merkwürdig aus.

in java nimmt man doch auch sicher Math.sqrt( potentialPrime ) aus dem schleifen kopf oder

lg javaNoob

icarus2

javaNoob schrieb:

icarus2 schrieb:

PS:
Auch in Java schreibt man <= statt < x + 0.5... das +0.5 sieht merkwürdig aus.

in java nimmt man doch auch sicher Math.sqrt( potentialPrime ) aus dem schleifen kopf oder

lg javaNoob

Warum?

icarus2 schrieb:

Warum?

darum! was soll die frage?

icarus2

Ich möchte nur wissen, warum man Math.sqrt( potentialPrime ) aus dem Schleifenkopf nimmt. Oder war das ironisch gemeint?

man nimmt alles aus dem schleifen kopf was nur einmal berechnet werden muß. vor allem sowas wie ein Math.sqrt(), du mußt nicht bei jedem schleifen durchlauf die wurzel ziehen, es reicht wenn du das einmal machst das ergebnis speicherst und dann bei jedem schleifen durchlauf das in einer variablen gespeicherte ergebnis für den vergleich hernimmst

icarus2

Ich habe es auf beiden Arten getestet. Es hat an der Rechenzeit überhaupt nichts geändert. Im Gegenteil... wenn ich das Math.sqrt(...) aus dem Schleifenkopf genommen habe gings sogar ein ganz kleines bisschen länger. Man kann aber sagen, dass es keinen Unterschied macht.

Die Compiler sind gut genug das selber zu regeln, das macht keinen Unterschied. Kannst es ja mal testen.

ja wenn das so ist dann weiter so...

mal eben die ersten 10000 primzahlen ausgeben =>

import java.math.BigInteger;

public class Prim
{
  public static void main(String[] args)
  {
    BigInteger prim = BigInteger.ONE;
    for (int i = 0; i < 10000; ++i)
    {
      prim = prim.nextProbablePrime();
      System.out.println(prim);
    }
  }
}

http://java.sun.com/javase/6/docs/api/java/math/BigInteger.html#nextProbablePrime()

Eisflamme

--

heißt die BigInteger klasse BigInteger weil man sie erst verwenden sollte, wenn das was man ausrechnen will nicht mehr in ein register passt

lg javaNoob

icarus2

Also wenn long zu kurz ist, dann nimmt man BigInteger oder BigDecimal. Die speichern die Zahlen speziell, sodass man meines Wissens nach mit beliebig grossen Zahlen rechnen kann.
Man sollte die Klasse aber nur verwenden wenn man sie wirklich braucht. Die arithmetischen Operationen, die für die beiden Klassen definiert sind, brauchen sicher länger als bei Primitivtypen.

javaNoob schrieb:

icarus2 schrieb:

PS:
Auch in Java schreibt man <= statt < x + 0.5... das +0.5 sieht merkwürdig aus.

in java nimmt man doch auch sicher Math.sqrt( potentialPrime ) aus dem schleifen kopf oder

Ne, der Java Compiler kann das selber rausoptimieren, im gegensatz zu nem C++ Compiler.

ich finde das sollte man aus stil gründen schon raus nehmen, allein aus dem grund das man weiß, dass derjenige der das programm geschrieben hat sich nicht voll auf den compiler als optimierer verlässt und weiß was er tut...

lg javaNoob

icarus2

JavaFördertSchlechtenStil schrieb:

ich finde das sollte man aus stil gründen schon raus nehmen, allein aus dem grund das man weiß, dass derjenige der das programm geschrieben hat sich nicht voll auf den compiler als optimierer verlässt und weiß was er tut...

Mann könnte aber auch auf Unwissen schliessen. Man könnte dann annehmen, dass der Programmiere nicht weiss, dass der Compiler das wegoptimiert. Auserdem ist dann eine zusätzliche Variable in der Methode drin... ist auch nicht unbedingt von Vorteil.
Naja, ist wohl Geschmackssache.

Ausserdem die Optimization Rules:
1. Don't do it
2. For experts only: Don't do it yet