Java, Primzahl berechnen.

Kann mir bitte jemand einen Link oder so schicken, will mal mit meinem Projekt vergleichen, das funzt irgendwie nicht richtig evt ist mein Rechnungsweg falsch.

oder kann mir jemand sagen wie die Rechnung für eine Primzahl zu finden geht ?

danke euch.

bool checkPrimzahl(int zahl)
{
    if(zahl == 0)
        return false;
    if(zahl == 1)
        return false;
    if(zahl == 2)
        return true;
//.. usw. Ist doch ganz easy MAN
}

ja ich mein dann muss ich ja tausende Zeilen tippen , kann man das net irgendwie aussrechnen ?

Andyman

Die Idee ist ganz simple jedoch was ist wenn man eine Zahl 5242245 hat, dann müsste man eine Abfrage bis ins unendliche machen. Besser wäre ein Algorithmus der die Zahl mit mod berechnet sodass man nicht auf eine festgelegte größe einer Zahl beschränkt ist. Denn somit hast du eine Funktion die kaum zu gebrauchen ist.

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.