Primfaktorzerlegung

[Guest]

Hallo,

ich würde gerne Zahlen in ihre Primfaktoren zerlegen.
Also beispielsweise:
30 = 2 * 3 * 5
oder
6936 = 2 * 2 * 2 * 3 * 17 * 17

Leider ist mein Algorithmus sehr ineffizient. Wie kann ich das schneller durchführen?


Hier mein Code:

public class PrimeFactors {
	
	public static void main(String[] args) {
		int a = 902313;
		ArrayList<Long> list = printPrimeFactors(a);
	    for(int i = 0;i<list.size();i++){
	    	System.out.print(list.get(i)+" ");
	    }
	}
	
	 public static ArrayList<Long> printPrimeFactors(long num){
		ArrayList<Long> primefactors = new ArrayList<Long>();
		long whichprime = 1;
		long prime;

	    while (num > 1) {
	      prime = getPrime(whichprime);
	      if (num % prime == 0) {
	    	  primefactors.add(prime);
	        num /= prime;
	      } else {
	        ++whichprime;
	      }
	    }
	    return primefactors;
	  }

	  public static long getPrime(long cnt)	  {
	    int i = 1;
	    int ret = 2;
	    while (i < cnt) {
	      ++ret;
	      if (isPrime(ret)) {
	        ++i;
	      }
	    }
	    return ret;
	  }

	  private static boolean isPrime(long num)	  {
	    for (long i = 2; i < num; ++i) {
	      if (num % i == 0) {
	        return false;
	      }
	    }
	    return true;
	  }

}

 

[Escorter]

     private static boolean isPrime(long num)     {
       for (long i = 2; i < num; ++i) {
         if (num % i == 0) {
           return false;
         }
       }
       return true;
     }

diese Methode kannst du verkürzen da du nur bis n % (n/2) bzw. n % wurzel(n) == 0 prüfen musst, weil alles was danach kommt musst du nicht mehr prüfen. Bei der ersten Varaient ist ja klar weil alles über der Hälfte hättest du ja schon in der ersten Hälte abgedeckt. Bsp: 12

1 * 12 = 12
2 * 6 = 12
3 * 4 = 12
----------- hälfte
4 * 3 = 12
...

Und irgend ein Mathematiker hat bewiesen das sogar reicht bis wurzel(n) zu prüfen. Kann dir aber leider nicht sagen warum das reicht. Aber es funktioniert

Gruß,
Esco

 

[SlaterB]

dazu brauchts nun wirklich keinen Mathematiker,
nimm dir n = 100
dann brauchst du für p = 11 nicht mehr zu prüfen, denn der zweite Faktor n/ p wäre kleiner als 10,
den hätte man also sowieso schon bei der vorherigen Suche für 1-10 gefunden

 

[Maeher]

Spar dir einfach die ganze Primzahlprüferei (bei dir riesiger Rechenaufwand). Dividier die Zahl so oft durch zwei bis es nimmer ohne Rest geht, dann durch 3, bis es nimmer geht, dann kannst du sie auf 4 prüfen, aber du hast sie ja sowieso schon oft genug durch 2 geteilt, es gibt hier also keinen Fehler...
Der Tipp oben gilt im Prinzip auch hier.

 

[Escorter]

dazu brauchts nun wirklich keinen Mathematiker,
nimm dir n = 100
dann brauchst du für p = 11 nicht mehr zu prüfen, denn der zweite Faktor n/ p wäre kleiner als 10,
den hätte man also sowieso schon bei der vorherigen Suche für 1-10 gefunden

Hmm stimmt, war mir irgentwie in dem Moment nicht eingefallen - ist heute nicht mein Tag :?


Gruß,
Esco

 

[0001001]

// ups vorhin vergessen einzuloggen

Vielen Dank für eure Vorschläge!
Hier meine verbesserte Version:

public class PrimeFactors {

	public static void main(String[] args) {
		long a = 902313;
		ArrayList<Long> fctr= primeFactors(a);
		for(int i = 0;i<fctr.size();i++){
			System.out.print(fctr.get(i)+" ");
		}
	}


	public static ArrayList<Long> primeFactors(long zahl){
		ArrayList<Long> liste = new ArrayList<Long>();
		long n = Math.abs(zahl); 
		
		if (n > 0) { 
			// 2er und 3er gesondert behandeln
			while (n % 2 == 0)  {
				liste.add((long)2);
				n /= 2;
			}
			while (n % 3 == 0)  {
				liste.add((long)3);
				n /= 3;
			}
			// rest
			for (int k = 5; k*k <= n; k += 6) {
				for (int dvsr = k; dvsr <= k+2; dvsr+=2) {
					while (n % dvsr == 0){
						liste.add((long)dvsr);
						n /= dvsr;
					}
				}
			}
			if (n > 1){
				liste.add((long)n);
			}
		}
		return liste;
	}
}

 

[Pappenheimer++]

Du kannst auch noch die Initialkapazität der ArrayList anpassen, um überflüssiges Umspeichern zu vermeiden.

 

[Leroy42]

...
			// rest
			for (int k = 5; k*k <= n; k += 6) {
				for (int dvsr = k; dvsr <= k+2; dvsr+=2) {
					while (n % dvsr == 0){
						liste.add((long)dvsr);
						n /= dvsr;
					}
				}
			}

Bist du sicher, daß das korrekt ist?

k += 6

:shock:

Also, irgendwie erschließt sich mir das jetzt nicht so richtig. ???:L

Aber, nun gut. Da ich jetzt zu faul bin die Korrektheit zu
beweisen, vertraue ich dir einfach mal.

Wenn das mein Chef hören/lesen würde...

 

[e9926044]

Also ich würd das ganze mit dem Euklidischen Algo machen. der ist sehr effizient und bei großen Zahlen geht es nicht schneller als mit diesem Algorihmus,
schau dir mal die wiki- Seite an:

http://de.wikipedia.org/wiki/Euklidischer_Algorithmus

da steht das ziemlich genau, wie man das macht und wenn man es richtig macht, dann braucht man nur Additionen und da ist man Performancemäßig ziemlich vorn dabei,

 

[Guest]

Also ich würd das ganze mit dem Euklidischen Algo machen. der ist sehr effizient und bei großen Zahlen geht es nicht schneller als mit diesem Algorihmus,
schau dir mal die wiki- Seite an:

http://de.wikipedia.org/wiki/Euklidischer_Algorithmus

da steht das ziemlich genau, wie man das macht und wenn man es richtig macht, dann braucht man nur Additionen und da ist man Performancemäßig ziemlich vorn dabei,

entweder versteh ich da was nicht oder der link ist ziemlich nutzlos... der eukl. algo dient zur bestimmung des GGT, nicht zur Pimzahlzerlegung... im wiki beitrag wird zwar erwaehnt, dass man zur bestimmung des ggts auch die zerlegung machen kann, aber in keinem wort ist was zu finden dass es anderesrum ebenso ist !

eine naive loesung waere zb auch

public class Test {
    public static void main( String[] args ) {
        long nr = 94522056262632L;
        int counter = 2;
        
        while ( counter <= ( int ) Math.sqrt( nr ) && nr > 1 ) {
            if ( nr % counter == 0 ) {
                nr /= counter;
                System.out.printf( "%s %s", counter, nr == 1 ? "" : "* " );
            }
            else {
                counter++;
            }
        }
        if ( nr != 1 ) {
            System.out.println( nr );
        }
    }
}