Rekursion größten Primfaktor finden funktioniert nicht

[sserio]

Hallo habt ihr eine idee wie man den größten Primfaktor mit hilfe einer Rekursion herausfindet? Bei mir ist es irgendwie ne endlosschleife, weil ich nicht weiß wie ich einen wert abspeicher, wenn der divider eine Primzahl ist und der andere nicht( wieder in die Rekursion) . Also falls ihr Tipps habt gerne stellen. Ps code kann unübersichtlich wirken:

package ProjectEuler3;

import java.util.List;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {
        for (int i = 0; i < findPrimeNumbers().size(); i++) {
            System.out.println(findPrimeNumbers().get(i));
        }
    }


    public static List<Integer> getPrimeFactor(int num) {
        List<Integer> list = new ArrayList<>();
        for (Integer n : findPrimeNumbers()) {
            if (num == n) {
                list.add(num);
                break;
            }
        }
        for (int i = 2; num % i != 0; i++) {
            if (num % i == 0) {
                for (Integer n : findPrimeNumbers()) {
                    if (num / i == n) {
                        if (i == n) {
                            list.add(i, num / i);
                        }
                    }
                    if (num / i == n && i != n) {
                        for (int p : getPrimeFactoR(i)) {
                            list.add(p);
                        }

                    } else if (num / i != n && i == n) {
                        for (int l : getPrimeFactoR(num / i)) {
                            list.add(l);
                        }

                    }
                }

            }
        }
        return list;
    }

    public static int[] getPrimeFactoR(int num) {
        int[] arr = new int[num];
        for (Integer n : findPrimeNumbers()) {
            if (num == n) {
                return new int[]{num};

            }
        }
        for (int i = 2; num % i != 0; i++) {
            if (num % i == 0) {
                for (Integer n : findPrimeNumbers()) {
                    if (num / i == n) {
                        if (i == n) {
                            int[] temp = new int[]{num / i, i};
                            arr = temp;
                        }
                    }
                    if (num / i == n && i != n) {
                        int[] temp = new int[]{num / i};
                        arr = temp;
                        getPrimeFactoR(i);
                    } else if (num / i != n && i == n) {
                        int[] temp = new int[]{i};
                        arr = temp;
                        getPrimeFactoR(num / i);
                    }
                }

            }
        }
        return arr;
    }

    public static List<Integer> findPrimeNumbers() {
        List<Integer> list = new ArrayList<>();
        int counter = 0;
        int zaehler = 0;
        for (int i = 2; i < 20000; i++) {
            for (Integer n : list) {
                if (isTrue(i, n)) {
                    counter++;
                }
            }
            if (counter == 0) {
                list.add(i);
                zaehler++;
            } else counter = 0;
        }
        return list;
    }

public static boolean isTrue(int n, int m) {
        return n % m == 0;
    }
}

 

[Gelöschtes Mitglied 65838]

schau dir bitte zuerst miches antwort an im anderen thread

Ps code kann unübersichtlich wirken:

er wirkt nicht nur so er ist es


der ansatz an dem ich mich erinnere ist

du probierst aus zb bei 40

2 * 2 => drunter
3 * 3 => drunter
...
6 * 6 => drunter
7 * 7 => drüber => stoppen ! und jetz wieder retour

40 % 7 == 0 ? nein also kleiner
40 % 6 == 0 ? nein also kleiner
40 % 5 == 0 ? ja

5 ist der größte primfaktor fürs erste

jetzt mathematik

5 * x = 40 // hat x einen größeren primfaktor als 5 ?
x  = 4 // nochmal prim faktor zerlegung bist du nur noch primfaktoren hast
// da 4 kleiner ist als der erste primfaktor kann man eig shcon aufhören
...
 
rekursiv zurück ist 2 ( ergebnis von prim zerlegung ) größer als 5 .. nö also 5 ist größte prim

du fragst dich warum man da wieder zurück rehcnen muss ?
zb bei 46 wäre prim zerlegung 23 aber durchs "ausprobieren" würdest du bei 7 * 7 aufhören dh du würdest die 23 nicht finden

[CODE lang="java" title="iterative lösung raus kopiert"] static long maxPrimeFactors(long n)
{
// Initialize the maximum prime
// factor variable with the
// lowest one
long maxPrime = -1;

// Print the number of 2s
// that divide n
while (n % 2 == 0) {
maxPrime = 2;

// equivalent to n /= 2
n >>= 1;
}
// n must be odd at this point
while (n % 3 == 0) {
maxPrime = 3;
n = n / 3;
}

// now we have to iterate only for integers
// who does not have prime factor 2 and 3
for (int i = 5; i <= Math.sqrt(n); i += 6) {
while (n % i == 0) {
maxPrime = i;
n = n / i;
}
while (n % (i + 2) == 0) {
maxPrime = i + 2;
n = n / (i + 2);
}
}

// This condition is to handle the case
// when n is a prime number greater than 4
if (n > 4)
maxPrime = n;

return maxPrime;
}

// Driver code
public static void main(String[] args)
{
Long n = 15l;
System.out.println(maxPrimeFactors(n));

n = 25698751364526l;
System.out.println(maxPrimeFactors(n));
}[/CODE]

[CODE lang="java" title="rekursive lösung in c"]#include <stdio.h>

long long prime_factor_i (int n, long long huge_number) {
while (n < huge_number) {
if (huge_number % n == 0) {
huge_number /= n;
continue;
}
n++;
}
return huge_number;
}

int main (void) {
int n = 2;
long long huge_number = 60085147514LL;
long long largest_prime = 0;

largest_prime = prime_factor_i (n, huge_number);
printf ("%lld\n", largest_prime);

return 0;
}[/CODE]

 

[Jw456]

die sich selbst aufrufebnde Methode "getPrimeFactoR" wird gar nicht gestartet weder in der main. In der for schleife
rufst du findPrimeNumbers() auf. Dort wird deine vermeitliche Rekusion auch nicht gestartet.

 

[sserio]

schau dir bitte zuerst miches antwort an im anderen thread


er wirkt nicht nur so er ist es


der ansatz an dem ich mich erinnere ist

du probierst aus zb bei 40

2 * 2 => drunter
3 * 3 => drunter
...
6 * 6 => drunter
7 * 7 => drüber => stoppen ! und jetz wieder retour

40 % 7 == 0 ? nein also kleiner
40 % 6 == 0 ? nein also kleiner
40 % 5 == 0 ? ja

5 ist der größte primfaktor fürs erste

jetzt mathematik

5 * x = 40 // hat x einen größeren primfaktor als 5 ?
x  = 4 // nochmal prim faktor zerlegung bist du nur noch primfaktoren hast
// da 4 kleiner ist als der erste primfaktor kann man eig shcon aufhören
...
 
rekursiv zurück ist 2 ( ergebnis von prim zerlegung ) größer als 5 .. nö also 5 ist größte prim

du fragst dich warum man da wieder zurück rehcnen muss ?
zb bei 46 wäre prim zerlegung 23 aber durchs "ausprobieren" würdest du bei 7 * 7 aufhören dh du würdest die 23 nicht finden

[CODE lang="java" title="iterative lösung raus kopiert"] static long maxPrimeFactors(long n)
{
// Initialize the maximum prime
// factor variable with the
// lowest one
long maxPrime = -1;

// Print the number of 2s
// that divide n
while (n % 2 == 0) {
maxPrime = 2;

// equivalent to n /= 2
n >>= 1;
}
// n must be odd at this point
while (n % 3 == 0) {
maxPrime = 3;
n = n / 3;
}

// now we have to iterate only for integers
// who does not have prime factor 2 and 3
for (int i = 5; i <= Math.sqrt(n); i += 6) {
while (n % i == 0) {
maxPrime = i;
n = n / i;
}
while (n % (i + 2) == 0) {
maxPrime = i + 2;
n = n / (i + 2);
}
}

// This condition is to handle the case
// when n is a prime number greater than 4
if (n > 4)
maxPrime = n;

return maxPrime;
}

// Driver code
public static void main(String[] args)
{
Long n = 15l;
System.out.println(maxPrimeFactors(n));

n = 25698751364526l;
System.out.println(maxPrimeFactors(n));
}[/CODE]

[CODE lang="java" title="rekursive lösung in c"]#include <stdio.h>

long long prime_factor_i (int n, long long huge_number) {
while (n < huge_number) {
if (huge_number % n == 0) {
huge_number /= n;
continue;
}
n++;
}
return huge_number;
}

int main (void) {
int n = 2;
long long huge_number = 60085147514LL;
long long largest_prime = 0;

largest_prime = prime_factor_i (n, huge_number);
printf ("%lld\n", largest_prime);

return 0;
}[/CODE]

was ist das eigentlich für eine Sprache? verstehe nur so die Hälfte davon

 

[Gelöschtes Mitglied 65838]

das erste ist java das zweite ist normales c

 

[sserio]

das erste ist java das zweite ist normales c

also ich habe es jetzt auf jeden Fall geschafft, jedoch habe ich irgedenwie ein problem mit der ausgabe:

package ProjectEuler3;

import java.util.List;
import java.util.ArrayList;

public class Main {

public static void main(String[] args) {
getBiggestPrimeNum(74414);
}

public static void getBiggestPrimeNum(int num) {
if (isPrime(num)) {
System.out.println(num);
} else {
for (int i = 2; i < num; i++) {
if (num % i == 0) {
if (isPrime(num / i)) {
System.out.println(num / i);
} else getBiggestPrimeNum(num / i);
}
}
}
}

public static List<Integer> findPrimeNumbers() {
List<Integer> list = new ArrayList<>();
int counter = 0;
for (int i = 2; i < 20000; i++) {
for (Integer n : list) {
if (isTrue(i, n)) {
counter++;
}
}
if (counter == 0) {
list.add(i);
} else counter = 0;
}
return list;
}

public static boolean isPrime(int num) {
for (Integer n : findPrimeNumbers()) {
if (num == n) {
return true;
}
}
return false;
}

public static boolean isTrue(int n, int m) {
return n % m == 0;
}
}

in dem Beispiel gibt er nicht einfach nur 1283 aus, sondern :
1283
29
1283
2
1283
29
2
29
2
EDIT: habe jetzt ein break an das 2te sout drangehangen und jetzt wird
1283
1283
1283
ausgegeben.
EDIT NUMMER 2: habe jetzt ein break an das 3te sout drangehangen und es funktioniert. Weiß aber nicht wieso jetzt das ergebnis aufeinmal nur noch einmal ausgegeben wird. Vllt wegen der rekursion oder so

 

[sserio]

also ich habe es jetzt auf jeden Fall geschafft, jedoch habe ich irgedenwie ein problem mit der ausgabe:

in dem Beispiel gibt er nicht einfach nur 1283 aus, sondern :
1283
29
1283
2
1283
29
2
29
2

wie macht man das eigentlich so, damit das wie echter code aussieht, also wie alle das hier eigentlich auf dem Forum machen

 

[Hansen_07]

Einfach oben links die Code-Tags benutzen ( </> )

 

[Gelöschtes Mitglied 65838]

wie macht man das eigentlich so, damit das wie echter code aussieht, also wie alle das hier eigentlich auf dem Forum machen

was meinst du damit ? du machst doch auch die code kasten