[Rust] Primfaktorzerlegung - größter Primfaktor einer Zahl

[Commodo]

let mut n: i64 = 600851475143;
let mut p: i64 = 2;

while (p <= n) {
if (n%p == 0) { n=n/p; continue }
else {p += 1; continue };
};

println!("{:?}", p);

}

Das funktioniert auch alles super. Aber warum ist der letzte Teiler einer Zahl Prim? Zumindest scheint es nach diesem Algorithmus so zu sein?

Ich hab unzählige Stunden damit verbracht einen Algorithmus für die Primfaktorzerlegung zu schreiben (teils wegen neuer Sprache und Nachschlagen von vielen Sachen), aber mein Programm ist deutlich größer und umfangreicher.

Hab den obigen Algo nachgebaut nachdem ich die Aufgabe gelöst und mir die Wege der anderen beim Euler-Projekt angeschaut habe, aber so ganz versteh ich nicht wie da auf Primzahl geprüft wird .

Aufgabe: https://projecteuler.net/problem=3

Mein Code nach 7 Stunden:

Spoiler

#![feature(core)]
use std::num::Float;

fn main () {
prime_fac();
}

fn prime_fac() {
let mut number: i64 = 600851475143;
let mut lower_limit: i64 = 2;
let mut upper_limit = (number as f64).sqrt() as i64 + 1;
let mut array_prime: Vec<i64> = vec![];

while (lower_limit < upper_limit) {
if (is_prime(lower_limit)) {
while (number % lower_limit == 0) {
array_prime.push(lower_limit);
number = number/lower_limit;
if (is_prime(number)) {array_prime.push(number); break;}
}
}
lower_limit += 1;
upper_limit = (number as f64).sqrt() as i64 + 1;
}
for p in array_prime.iter() { println!("{:?}", p) };
}



fn is_prime(i: i64) -> bool {

let float_grenze = (i as f64).sqrt() as i64 + 1;
let grenze = float_grenze as i64 + 1;
if (i > 1 && i <= 3) { return true }
else { for k in range(2, grenze) { if (i % k == 0) { return false } } }
return true
}

 

[MingsPing]

Edit:
Sorry, hab den Algorithmus doch nicht genügend genau angeschaut. Tatsächlich berechnet er den größten Primfaktor.

Ich erkläre dir den Algorithmus mal anhand eines Beispiels: Sagen wir wir wollen den größten Primfaktor von 300 bestimmen. 300 = 2*2*3*5*5 also 5.

1. n := 300, p := 2
2. n%2 = 0 -> n:=n/2 = 150
3. n%2 = 0 -> n:=n/2 = 75
4. n%2 !=0 -> p:=p+1 = 3
5. n%3 = 0 -> n:=n/3 = 25
4. n%3 !=0 -> p:=p+1 = 4
5. n%4 !=0 -> p:=p+1 = 5
6. n%5 = 0 -> n:=n/5 = 5
7. n%5 = 0 -> n:=n/5 = 1
8. p > n
9. print p = 5

Der Knackpunkt liegt darin, dass n in jeder Iteration, in der n%p = 0 erfüllt ist, durch dieses p geteilt wird. Und das so lange, bis p kein Teiler mehr von n ist. Man sieht es an p = 2. 300 ist eigentlich durch 4 teilbar. Dies wird jedoch nicht ausgegeben, da zuvor schon n zweimal durch 2 geteilt wurde und somit das neue n nicht mehr durch 4 teilbar ist.
genau so ist es mit z.B. 10. 10 teilt 300, da aber zweimal durch 2 geteilt wurde, ist 10 kein Teiler mehr von 75.
Die Zahlen, die keine Primzahlen sind (z.B. 10), können also im späteren Verlauf keine Teiler mehr sein, da deren Primfaktoren (z.B. 2 und 5, 2*5=10) wiederum zuvor schon aus n herausgeteilt wurden.

 

[Commodo]

Darauf wäre ich nie gekommen .... Aber wie wird sichergestellt, dass alle Teiler Primzahlen sind?
Ich sehe zwar dass 2,3,5,7 quasi alle anderen Vielfachen "erschlagen", aber ist einfach nur glücklicher Zufall den man sich da zunutze macht oder steckt da irgendein mathematischer Beweis dahinter, auf den sich dieser Algorithmus stützt?

 

[MingsPing]

Ja, dass immer nur Primzahlen entstehen ist nicht glücklicher Zufall (vllt. ist man darauf zuerst durch Zufall gekommen) sondern kann bewiesen werden.
Hier mal meine Beweisidee mittels Widerspruchsbeweis:

Angenommen, in irgend einem Schritt gibt es ein p1, das ein Teiler von n ist, aber keine Primzahl. Also gilt
n % p1 = 0 und
p1 = a*b mit a,b < p1 (Es gibt zwei echte Teiler von p1)

Daraus folgt aber, dass in dem Schritt, in dem
n % a getestet wurde, mindestens 1 mal zu wenig n := n / a gerechnet wurde (klar, denn sonst könnte n%p1 = 0 nicht stimmen).
Damit gilt also auch n%a = 0.
Das ist aber ein Widerspruch zum Algorithmus, da dieser das p erst erhöht, wenn n%p != 0 ist (bzw. das p=a erst auf a+1 erhöht, wenn n%a != 0 ist).

Also gilt insgesamt: Unsere Annahme, es gäbe ein solches p1, ist falsch.

 

[Timon3]

Stell es dir einfach mal so vor: Wenn du eine Zahl n durch einen Faktor p teilen kannst, der nicht prim ist, kannst du n ja auch durch jeden einzelnen Primfaktor von p teilen. Die Primfaktoren einer Zahl müssen zwingend kleiner sein, als die Zahl selbst - also werden sie zuerst versucht. Wenn eine Zahl also nicht mehr durch einen Primfaktor teilbar ist, kann sie ja auch nicht durch ein Vielfaches dieses Primfaktors teilbar sein, weil sie dafür ja durch den Primfaktor teilbar sein müsste.

 

[Commodo]

Hier mal meine Beweisidee mittels Widerspruchsbeweis:

Ich kann mit mathematischen Beweisen nicht wirklich was anfangen mit meinem beschränkten Intellekt, aber Danke für die Erklärung .