Primfaktorenzerlegung

[Bierjunkie]

Hallo,

habe das Problem Nummer 3 von Project Euler bearbeitet!

Aufgabenstellung:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

package problem_3;


public class Prim {


	public static void main(String[] args) {

		long n = 600851475143L; 
		for (long i = 2; i <= n; i++) {
			if (n % i == 0) { 
				System.out.println("Primfaktor:	" + i); 
				
				n = n / i;
				i = 2;
			}
		}

		System.out.println();

	}

}

Nun frage ich mich wieso folgender Abschnitt ohne Überprüfung auf Richtigkeit(Primfaktor ja oder nein) korrekt abgearbeitet wird und warum:

if (n % i == 0) { 
				System.out.println("Primfaktor:	" + i); 
				
				n = n / i;
				i = 2;
			}

 

[SlaterB]

nochmal neu, was ist deine Frage?
der Code prüft ob die Zahl ein Teiler ist, das ist doch zu verstehen?
dass es auch ne Primzahl ist ergibt sich durch die Reihenfolge, es wird immer von 2 aus gestartet,
9 kann dabei nicht herauskommen denn dann wäre schon bei 3 die Runde beendet

 

[Bierjunkie]

Wie der Code arbeitet ist mir klar!Doch könnte man auch hier eine Methode in dieser Form hinzufügen, ob es sich hierbei wirklich um eine Primzahl handelt. Könnte dem Leser nicht ganz klar sein, wieso etwas richtig oder falsch ist.

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

Bezug zum ersten Programm:

Wenn es sich um einen Primfaktor handelt,wird dieser ausgegeben!Doch wenn es sich hierbei nicht um eine Primzahl/Primfaktor handelt, arbeitet es einfach die Schleife solange ab, bis ein weiterer Primfaktor getroffen wird und gibt diese in einer neuen Zeile aus?!

 

[SlaterB]

beschreiben wir Offensichtlichkeiten? die Sonne ist gelb

lass das Programm doch laufen,
oder überlege in Ruhe im Kopf was passiert

> arbeitet es einfach die Schleife solange ab, bis ein weiterer Primfaktor getroffen wird
wenn du dir dazu nicht sicher bist, was hast du denn als Alternative in der Vorstellung?

 

[Bierjunkie]

beschreiben wir Offensichtlichkeiten? die Sonne ist gelb

lass das Programm doch laufen,
oder überlege in Ruhe im Kopf was passiert

> arbeitet es einfach die Schleife solange ab, bis ein weiterer Primfaktor getroffen wird
wenn du dir dazu nicht sicher bist, was hast du denn als Alternative in der Vorstellung?

Ich habe keine Alternative im Sinn! Dennoch möchte ich gerne exakt wissen wie der Berechnungsblock ohne Überprüfung einer Methode á la isPrime arbeitet/ausgibt.

 

[SlaterB]

> arbeitet es einfach die Schleife solange ab, bis ein weiterer Primfaktor getroffen wird und gibt diese in einer neuen Zeile aus?!
ja

 

[Bierjunkie]

Sehr gut.Da wäre nur noch eine Sache!

if (n % i == 0) { 
                System.out.println("Primfaktor: " + i); 
                
                n = n / i;
                i = 2;

Wie genau funktioniert/arbeitet n=n/i; i=2;?Funktioniert es etwa so das wenn eine Zahl n%i != 0 kein Primfaktor ist,das Ergebnis solange weiterverarbeitet wird ,bis ein Primfaktor als Ergebnis berechnet und ausgegeben wird?!

 

[SlaterB]

ist das nicht vollkommen dieselbe Frage?
ja, i wird erhöht bis ein Faktor gefunden wird.., dann gehts wieder von vorne los,
das Teilen bewirkt dass nicht exakt dasselbe passiert, sonder dass ein weiterer Teiler gesucht wird