Commodo
NGBler
- Registriert
- 17 Mai 2014
- Beiträge
- 151
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:
#![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
}