# Primfaktorzerlegung



## Guest (18. Apr 2008)

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 (18. Apr 2008)

```
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 (18. Apr 2008)

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 (18. Apr 2008)

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 (18. Apr 2008)

SlaterB hat gesagt.:
			
		

> 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 (18. Apr 2008)

// 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++ (18. Apr 2008)

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


----------



## Leroy42 (21. Apr 2008)

0001001 hat gesagt.:
			
		

> ```
> ...
> // rest
> for (int k = 5; k*k <= n; k += 6) {
> ...



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 (22. Apr 2008)

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 (22. Apr 2008)

e9926044 hat gesagt.:
			
		

> 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
> ...


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 );
        }
    }
}
```


----------

