Zerlegung in Primzahlen

[Nik87]

Hallo,

wir sollen ein Javaprogramm schreibe, daß zu einer Eingabezahl die Primfaktorenzerlegung ausgibt. Dabei sollen beliebig große Zahlen auf der Konsole eingegeben werden können (d.h. es ist die Klasse BigInteger zu verwenden). Die Zahlen sollen mit println ausgegeben werden. Als Test der Korrektheit sollen 400000000000000000001 und 900000000000000000001 zerlegt werden.

Na ja, ich hab mir das so gedacht: ich teste alle Zahlen von 2 bis x, ob sie Teiler der Zahl sind. Das ist der Fall, wenn die Division den Rest 0 ergibt (das ist hier die remainder-Funktion). Hier mein bisheriges Programm (das soll nicht ganz richtig sein):

import java.math.*;

public class Faktor
{
	public static String Zerlegung(BigInteger N)
	{
		if (N.compareTo(BigInteger.valueOf(1)) == 0) return "1";
		String Resultat = "";
		BigInteger Fak = new BigInteger("1");
		BigInteger Null = BigInteger.valueOf(0);
		for (int i = 2; i <= 10000000; i++)
		{
			Fak = BigInteger.valueOf(i);
			if (N.remainder(Fak).compareTo(Null) == 0)
			{
				Resultat = Resultat + Fak.toString() + " * ";
			}
		}
		return Resultat;
	}

	public static void main(String[] args)
	{
		System.out.println(Zerlegung(new BigInteger(args[0])));
	}
}

Mittlerweile hab ich mir sagen lassen, dass man nur bis zur Wurzel gehen braucht, aber wie berechnet man die Wurzel bei BigIntegern? Also muß ich vorerst ein festes x nehmen.
Wir sollen das Proggie auch effizient schreiben ,die ganze Sache ist aber ziemlich langsam, die erste Testzahl geht ja noch irgendwie, bei der zweiten dauerts schon.
Wie würdet ihr die Sache aufziehen oder was könnte ich ändern?

 

[bygones]

ich kann dir leider momentan kein bessern algorithmus liefern, nur ein paar anmerkungen die man machen sollte

1. keine Stringanhängungen ... also kein + für Strings verwenden, wenn dann StringBuilder bzw. StringBuffer

2. valueOf ist schon gut, aber für 0 & 1 hat BigInteger sogar eigene Konstanten... nutze die

ansonsten gibts hier ne version mit long http://www.pi.informatik.tu-darmsta...ardcode/java/math/SpecialMath.html#primfaktor kannst ja vielleicht ummodeln ^^

 

[Romeus]

Dein Programm gibt nicht die Primfaktorzerlegung aus sondern alle möglichen Teiler < x. Der kleinste Teiler, der gefunden wird, ist natürlich eine Primzahl - und sobald man den gefunden hat, sollte man ihn aus der Eingabezahl herausdividieren, da sich dann die Quadratwurzel verkleinert. Ich weiß zwar auch nicht, wie man die Wurzel bestimmt, aber vielleicht folgende Überlegung: Die Wurzel besitzt etwa die halbe Bitlänge, so daß man mit

BigInteger.bitLength()

eine Zahl konstruieren kann, die in der Nähe der Wurzel liegt.
Bedenke, daß Primteiler mehrfach vorkommen können und man nicht jede Zahl als potenziellen Teiler abchecken muß.

 

[bygones]

die wurzel zu bekommen ist scheinbar nicht wirklich trivial
siehe auch http://www.codecomments.com/archive252-2004-8-240213.html

ansonsten - am besten nur die Primzahlen durchlaufen (nextProbablePrime()) und bei einem treffer dran denken, dass die Primzahl mehrfach drinnen vorkommen kann

 

[SnooP]

Wie wär's mit dem Heron-Verfahren?

public int heron(double a) {
double x = 1.0,
y;
for (int i = 1; i <= 7; i++) {
y = (x + a / x) / 2.0;
x = y;
}
return x;
}

Liefert die Quadratwurzel von a...

 

[Romeus]

Genauso läufts! Hier das Heronverfahren für BigInteger:

static BigInteger Wurzel(BigInteger N)
{
	BigInteger Alpha = BigInteger.ONE.shiftLeft(N.bitLength()/2);
	BigInteger Beta;
	BigInteger Zwei = BigInteger.valueOf(2);
	do
	{
		Beta = N.divide(Alpha);
		Alpha = (Alpha.add(Beta)).divide(Zwei);
	} while (Alpha.subtract(Beta).abs().compareTo(Zwei) >= 0);
	return Alpha;
}

Das muß natürlich entsprechend eingebunden werden.

 

[Diablo]

Es bietet sich an, die Routine rekursiv auf den Komplementärteiler anzuwenden, falls ein Teiler gefunden wird.
Bei einer Testdivision braucht man auch nur die ungeraden Zahlen zu testen, falls man die 2 als Teiler ausgeschlossen hat. Denkt man den Gedanken weiter, so braucht man nur 2, 3 und danach alle Zahlen der Form 6n±1 zu testen (um Vielfache von 3 wie z. B. 15 auszuschließen). Oder 2, 3, 5 und danach alle 30n±1, ±7, ±11, ±13 usw.

Noch effizienter ist folgendes Programm (Kannst es gerne so übernehmen :wink: ):

import java.math.*;

public class Faktor
{
	public static String FastFac(BigInteger N)
	{
		BigInteger Fak1, Fak2;
		String Rest;
		if (N.compareTo(BigInteger.ONE) == 0) return "";
		for (int i = 2; i <= 19; i++)
		{
			Fak1 = BigInteger.valueOf(i);
			if (N.remainder(Fak1).compareTo(BigInteger.ZERO) != 0) continue;
			Fak2 = N.divide(Fak1);
			Rest = FastFac(Fak2);
			if (Rest == "") return Fak1.toString();
			else return Fak1.toString() + " * " + Rest;
		}
		if (BigInteger.valueOf(2).compareTo(BigInteger.valueOf(2).modPow(N, N)) == 0) return N.toString();
		BigInteger A = BigInteger.ONE;
		BigInteger B = BigInteger.ONE;
		while (true)
		{
			A = A.pow(2).add(BigInteger.ONE).remainder(N);
			B = B.pow(2).add(BigInteger.ONE).remainder(N).pow(2).add(BigInteger.ONE).remainder(N);
			Fak1 = B.subtract(A).gcd(N);
			if (Fak1.compareTo(BigInteger.ONE) == 0) continue;
			Fak2 = N.divide(Fak1);
			return Fak1.toString() + " * " + FastFac(Fak2);
		}
	}

	public static void main(String[] args)
	{
		System.out.println(FastFac(new BigInteger(args[0])));
	}
}

Die Programmausgabe ist demnach:

java Faktor 400000000000000000001
17 * 53 * 29 * 1129 * 5953 * 63389 * 35933

java Faktor 900000000000000000001
1669850621 * 538970365781

Die zweite Zahl wird bei mir in ca. 1 Sekunde zerlegt.

 

[Guest]

@diablo: sehr gut dein algorithmus
kannst du ihn mir vielleicht näher erklären?