nicht angemeldet
Hallo Struppi,
Irgendwo in diesem Thread wurde auf ein C++ Forum verweisen, wo vorgeschlagen wurde, Fakultäten mittels Primfaktorzerlegung zu berechnen. Ich habe mal einen Algorithmus gebastelt, der zwar sicher noch nicht optimal, aber schon sehr viel schneller als die herkömmliche rekursive oder iterative Variante ist.
Die Berechnung von 100000! braucht bei mir 5 min, wenn man den Algorithmus mit so großen Zahlen testet, sollte man allerdings die Ausgabe auskommentieren, da sie mehr Zeit als die eigentliche Berechnung benötigt. Schneller als die herkömmliche, rekursive implementierung ist der Algorithmus allerdings erst ab 1500.
import java.util.*;
import java.math.BigInteger;
public class factorial {
public static final void main(String[] args) {
int n = 10000;
long time1 = System.currentTimeMillis();
//Berechnung der Primfaktoren
Map<Integer, Integer> primes = getPrimes(n);
long time2 = System.currentTimeMillis();
BigInteger factorial = BigInteger.ONE;
//Berechnung der Fakultät mit Hilfe der Primfaktoren
for(Map.Entry<Integer, Integer> entry: primes.entrySet()) {
factorial = factorial.multiply(BigInteger.valueOf(entry.getKey()).pow(entry.getValue()));
}
long time3 = System.currentTimeMillis();
System.out.println(n + "! =" + factorial.toString(36));
System.out.println("Primfaktoren: " + (time2 - time1));
System.out.println("Multiplikation: " + (time3 - time2));
System.out.println("Gesamt: " + (time3 - time1));
}
//Gibt die Primfaktoren der Fakultät von n zurück.
static Map<Integer, Integer> getPrimes(int n) {
BitSet raster = new BitSet(n - 1);
Map<Integer, Integer> primes = new TreeMap<Integer, Integer>();
int prime = 0;
while(prime != -1) {
primes.put(prime + 2, mark(prime, raster, n));
prime = next(prime, raster, n);
}
return primes;
}
//Markiert einen Primfaktor und berechnet seine Häufigkeit
static int mark(int prime, BitSet raster, int n) {
int count = 0;
for(int i = prime; i < n - 1; i += prime + 2) {
raster.set(i, true);
}
prime += 2;
for(int i = prime; true; i *= prime) {
int z = (int)Math.floor(n / i);
if(z == 0) {
break;
}
count += z;
}
return count;
}
//Gibt den nächsten Primfaktor zurück oder -1 wenn es keinen mehr gibt.
static int next(int prime, BitSet raster, int n) {
for(;prime < n - 1; prime++) {
if(!raster.get(prime)) {
return prime;
}
}
return -1;
}
}
Grüße
Daniel