Problem versuchen Projekt Euler # 3

Question

Ich versuche, Projekt Euler Nummer drei zu lösen, aber ich bin ziemlich durcheinander mit der Logik, um die Berechnung zu stoppen.

Hier ist das Projekt Euler Nummer drei:

Die Primfaktoren von 13195 sind 5, 7, 13 und 29

Was ist der größte Primfaktor der Nummer 600851475143?

Nun, habe ich eine Funktion zu überprüfen, ob die Zahl eine Primzahl ist:

public static boolean isPrime(int number) { 
    if (number % 2 == 0) 
     return false; 

    for (int i = 3; i*i <= number; i+=2) { 
     System.out.println("Dividing the number " + number + " by: " + i); 
     if (number % i == 0) 
      return false; 
    } 
    return true; 
} 

Und eine Funktion zu überprüfen, ob die Primzahl ein Faktor der Nummer lautet:

public static boolean isFactor(int number, int prime) { 
    if (number % prime == 0) 
     return true; 
    else 
     return false; 
} 

Nur Problem ist die Hauptfunktion, ich versuche etwas in der Art:

public static void main(String[] args) { 

    int number = 13195; 
    int i = 3; 

    do { 
     i++; 
    } while (isPrime(i) && isFactor(number, i) == false); 

    System.out.println(i); 

} 

Ich weiß, dass die Logik nicht stimmt, aber ich bin wirklich länger als eine Stunde dran.

Ich weiß, dass das Hauptziel hier ist, zu loopen, eine Primzahl zu finden und zu überprüfen, ob diese Primzahl ein Faktor der Zahl ist und die größte findet, aber die Stoppbedingung wäre, wenn die Schleifenzahl eine Primzahl ist und nicht ist ein Faktor der Anzahl.

Sorry für das Chaos, ich bin ziemlich fest :) danke!

Answer 1

Das Hauptproblem mit Ihrer Logik ist, dass Sie mit der kleinsten Primzahl beginnen, und sobald es eine Zahl trifft, die Primzahl ist und ein Faktor einer gegebenen Zahl, stoppt Ihr Programm. Was Sie tun sollten, ist vom anderen Ende zu starten. Da wir jede Primdivisor einer Anzahl nicht wissen, als Quadratwurzel der Anzahl größer sein, so können Sie tun, ist:

int number = 13195; 
int i = (int)Math.sqrt(number); 

do { 
    i--; 
} while (isPrime(i) && isFactor(number, i) == false); 

System.out.println(i); 

Es gibt noch weitere Änderungen für 600.851.475.143, das nicht in int passt so versuchen um lange zu verwenden, wo immer Sie die Berechnung machen.

Hier ist meine Lösung für diese Frage, es ist nicht 100% richtig, aber es funktioniert für diese Frage.

public static void main(String[] args) { 
    long number= 600851475143L; 
    int rootOfNumber = (int)Math.sqrt(number)+10; 
    for(int i = rootOfNumber; i > 2; i--) { 
     if(number % i == 0) { 
      if(psudoprime(i)) { 
       System.out.println(i); 
       break; 
      } 
     } 
    } 

} 

public static boolean psudoprime(int num) { 
    for(int i = 2; i < 100; i++) { 
     if(num % i == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

Answer 2

Die Schleife im Hauptcode stoppt nach dem Finden des ersten Primendivisors der genannten Nummer. Wir müssen stattdessen alle solchen Hauptteiler eliminieren, bis wir die größten unter ihnen erreichen. Ich zögere, irgendeinen Code hier zu teilen, weil die Frage wirklich spezifisch ist. Anstatt die Schleife beim Auftreten eines Prim Divisors zu unterbrechen, versuchen Sie alle aufzulisten.

Hoffe, das hilft.

Answer 3

public class LargestPrimeFactor { 
private long num; 
public LargestPrimeFactor(long num){ 
    this.num=num; 
} 
public long calculate(){ 
    for(long i=1;i<=num/2;i++) 
     if(num%i==0) 
      if(isPrime(num/i)) 
       return num/i; 

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