Primfaktorzerlegung m. kleinem Fermat-Satz

[Unix1]

Guten Abend,
ich sitze gerade am Problem nr.3 von "Project Euler".https://projecteuler.net/problem=3
Es geht um die Primfaktorzerlegung einer großen Zahl und Ermittlung des größten Faktors. Nun wollte ich den kleinen Satz von Fermat als Primzahltest hinzuziehen.https://de.wikipedia.org/wiki/Fermatscher_Primzahltest
Doch es funktioniert nicht, alle Vielfachen der bereits gefundenen Primzahlen werden einfach in die Primzahlenliste aufgenommen(bspw. 15, 9, etc).
Hier werden die Zahlen generiert:

prims = new ArrayList<Double>();
		factors = new ArrayList<Double>();
		//Generate a list of prims below a certain limit
		for(double i = 2; i < 20; i++){
			//Leave out all multiples of 2 and exclude all even-valued numbers;
			//reduces the runtime of this algorithm.
			if(i%2==0)
				continue;
			if([B]isPrim(i)[/B])
				prims.add(i); }

Die Implementierung des kl. Fermat-Satzes:

private boolean isPrim(double n) {
		//Choose a as a number 1<a<p
		double a = 2;
		//If a**(n-1) mod n == 1 mod n, n is prim
		if(((Math.pow(2, (n-1))-1)%n)==1)
			return true;
		//Otherwise, if a**(n-1) mod n == y mod n, 1<y<n so y != 1, n can be factorized and is not prim
		return false;
	}

Hier die Hauptmethode:

      double calc(double value) {
                int i = 0;
		//Return -1 if the number is prim itself
		double biggest = -1;
		if(isPrim(value)) {
			//detect the biggest of the factors;
			biggest = getMax();
			return biggest;
		}
		//passed value is not prim:
		for(; i < prims.size(); i++) {
			//If we have found a real prim divisor:
			if((value%prims.get(i))==0 && !(factors.contains(prims.get(i))))
				factors.add(prims.get(i));
				i = prims.size();
		}
		//You found one factor, now let's split up the other one until it is a prim itself.
		calc(value/factors.get(i));
		return biggest; }

Das Prinzip: calc() arbeitet rekursiv. Es wird eine Primzahl gesucht, die Teiler von dem eingegebenen Wert ist. Nun ist der andere Faktor folglich: (eingegebenerWert)/(gefundenenFaktor). Nun wird dieser Wert zerlegt. Das ganze endet, wenn der zu zerlegende Wert selbst prim ist.
Ich habe schon die SuFu benutzt, aber nichts hilfreiches bzgl. der Implementierung des kleinen Fermat-Satzes erhalten, will es unbedingt damit versuchen, es muss doch schließlich damit auch funktionieren.
Vielen Dank im voraus.

 

[Unix1]

Habe den Fehler der Implementierung heute morgen selbst gefunden. Sehr dummer Fehler
Korrektur:

private boolean isPrim(double n) {
        //Choose a as a number 1<a<p
        double a = 2;
        //If a**(n-1) mod n == 1 mod n, n is prim
        if(((Math.pow(2, (n-1)))%n)==1)
            return true;
        //Otherwise, if a**(n-1) mod n == y mod n, 1<y<n so y != 1, n can be factorized and is not prim
        return false;
    }

Die Subtraktion der 1 in (Math.pow(a, (n-1))%n) war überflüssig. Nun gibt es aber einen StackOverflowError wenn man in die Hauptmethode als Wert 18 eingibt. Bei 9 klappt das Problem wunderbar, bei 21 wiederum nicht, da nur 3 als größter Primfaktor ausgegeben wird, dieser aber bekanntlich die 7 ist. Ich poste gleich genaueres!

 

[Unix1]

	/**A recursive method to identify the divisors of a number.*/
	public double calc(double value, int start) {
		boolean found = false;
		int i = start;
		//Return 1 if the number is prim itself
		if(isPrim(value)) {
			//detect the biggest of the factors; sort the ArrayList in some way
			return getMax();
		}
		//value is not prim
		for(; i < prims.size() && !found; i++) {
			//If we have found a real prim divisor which is not already in the list 'factors':
			if((value%prims.get(i))==0 && !(factors.contains(prims.get(i)))) {
				factors.add(prims.get(i));
				found = true;
			}
		}
		//You found one factor, now let's split up the other one until it is a prim itself.
		//TODO StackOverflowError when choosing 18 as the value!!!
		calc(value/factors.get(factors.size()-1), 0);
	//TODO This part of the method should not be accessed!!! It should end at the first if-clause as there is a return-
		//instruction!!!
		System.out.println("Wrong");
		return getMax();
	}

Hier die Meldung, die ich erhalte, wenn ich 18 als einzugebenden Wert wähle:

Exception in thread "main" java.lang.StackOverflowError
	at java.util.ArrayList.indexOf(Unknown Source)
	at java.util.ArrayList.contains(Unknown Source)
	at ID3.calc(ID3.java:44)
	at ID3.calc(ID3.java:54)
	at ID3.calc(ID3.java:54)

 

[Kevin94]

Für den StackOverFlowError hab ich eine Erklärung: Wenn ein Primfaktor mehr als einmal auftritt und die Zahl nicht eine Quadratzahl einer Primzahl ist, landest du in einer endlos Rekursion.
[JAVA=18]if((value%prims.get(i))==0 && !(factors.contains(prims.get(i)))) {[/code]
Es müsste aber auch ausgeführt werden wenn, der Faktor schon einmal vorhanden war. Ich würde die Faktoren in einem Set speichern und den Rekursiven Aufruf direkt in der Schleife machen. (Anstatt found würde ich übrigens ein break setzen.)
[EDIT]Oder direkt return calc(); in der Schleife, wäre am sinvollsten.[/EDIT]

Und das bei 21 das falsche raus kommt auch:
[JAVA=6] if(isPrim(value)) {
//detect the biggest of the factors; sort the ArrayList in some way
return getMax();
}
[/code]
Hier müsstest du vor getMax() value noch zu den Faktoren hinzufügen, in der Regel dürfte die Primzahl die am Ende übrigbleibt, immer die größte sein, blick den Algorithmus aber nicht genaugenug durch um sagen zu können, ob das immer der Fall ist.

 

[Unix1]

Danke Kevin94. Ich habe mich jetzt einfach mal hingesetzt und es ohne Rekursion versucht:

/**Same method like calc but not recursive.*/
	public double calc2(double value) {
		//Use a boolean-variable to control the outer loop
		boolean quit = false;
		for(;!quit; ) {
			int i = 0;
			//Traverse the ArrayList, finde real divisors of the value.
			//When having found one divisor quit the inner loop and set the value
			//you want to split up to the other factor!!! 
			//foundPrim*otherFactor=value;
			//value = otherFactor;
			for(; i < prims.size(); i++) {
				if(value%prims.get(i)==0) {
					factors.add(prims.get(i));
					System.out.println(""+prims.get(i));
					break;
				}
			}
			//Found no more real divisors, so i==prims.size() when quitting the for-loop:
			if(i < prims.size())	
				value = value/prims.get(i);
			else//No more real divisors were found in prims so i==prims.size():
				quit = true;
		}
		return getMax();
	}

Und es hat auf Anhieb funktioniert. Ich werde mich wenn ich Zeit habe nochmal an die Implementierung mit der Rekursion wagen in den nächsten Tagen!