Primfaktorzerlegung mit Rust

Das Programm “primfaktorzerlegung” verwendet die Bibliothek prime_factorization zur Berechnung der Primfaktorzerlegung einer gegebenen 128-Bit-Ganzzahl und gibt die Ergebnisse in einer formatierten Ausgabe aus, einschließlich der hochgestellten Exponenten für wiederholte Primfaktoren und der Prüfung, ob die Zahl eine Primzahl ist und zeigt die Ausführungszeit in Millisekunden an.

Beispiele

Primzahlentest für 2² × 3² × 5² × 7² × 11² × 13² × 19²

Primfaktoren von 325550124900:
2² × 3² × 5² × 7² × 11² × 13² × 19²
Ist eine Primzahl: false
Programm benötigte 0.006 Millisekunden zur Ausführung.

Primzahlentest für 2² × 3² × 5² × 7² × 11² × 13² × 19² + 1

Primfaktoren von 325550124901:
325550124901
Ist eine Primzahl: true
Programm benötigte 0.564 Millisekunden zur Ausführung.

Primzahlentest für 11111111111111111111111

Primfaktoren von 11111111111111111111111:
11111111111111111111111
Ist eine Primzahl: true
Programm benötigte 2.414 Millisekunden zur Ausführung.

Primzahlentest für 2¹²⁷ – 1

Primfaktoren von 170141183460469231731687303715884105727:
170141183460469231731687303715884105727
Ist eine Primzahl: true
Programm benötigte 0.109 Millisekunden zur Ausführung.

Primzahlentest für 2¹²⁷

Primfaktoren von 170141183460469231731687303715884105728:
2¹²⁷
Ist eine Primzahl: false
Programm benötigte 0.013 Millisekunden zur Ausführung.

Primzahlentest für das Produkt der ersten 26 Primzahlen (Primzahlenfakultät)

Primfaktoren von 232862364358497360900063316880507363070:
2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 × 23 × 29 × 31 × 37 × 41 × 43 × 47 × 53 × 59 × 61 × 67 × 71 × 73 × 79 × 83 × 89 × 97 × 101
Ist eine Primzahl: false
Programm benötigte 0.010 Millisekunden zur Ausführung.

Crate prime_factorization

Das Programm implementiert eine Funktion zur Primfaktorzerlegung von natürlichen Zahlen. Hier ist eine schrittweise Beschreibung dessen, was das Programm tut:

1. Trial Division (Versuchsteilung):
   Das Programm verwendet eine Technik namens “Trial Division” mit den ersten 1006 Primzahlen. Es versucht, die gegebene Zahl durch diese Primzahlen zu teilen, um die kleinsten Primfaktoren zu finden. Wenn ein Primfaktor gefunden wird, wird er der Liste der Faktoren hinzugefügt, und die Zahl wird durch den Primfaktor geteilt. Dies wird wiederholt, bis die Zahl nicht mehr durch eine der Primzahlen teilbar ist.
2. Fermats Faktorisierungsmethode:
   Wenn die Trial Division abgeschlossen ist und die Zahl immer noch größer als 1 ist, wird Fermats Faktorisierungsmethode angewendet. Diese Methode versucht, die Zahl in zwei Quadratzahlen aufzuteilen (n = a² – b²). Wenn dies gelingt, sind a und b die Faktoren von n. Dieser Schritt wird rekursiv wiederholt, bis keine weiteren Faktoren gefunden werden können.
3. Primzahltest:
   Nach der Fermat-Methode wird überprüft, ob die verbleibende Zahl eine Primzahl ist. Dazu werden die Miller-Rabin- und Baillie-PSW-Primzahltests verwendet. Wenn die Zahl als Primzahl erkannt wird, wird sie der Liste der Faktoren hinzugefügt.
4. Elliptische Kurven-Faktorisierung:
   Wenn die Zahl immer noch größer als 1 ist und nicht als Primzahl erkannt wurde, wird die elliptische Kurven-Faktorisierungsmethode angewendet. Dies ist ein komplexerer Algorithmus, der versucht, nicht-triviale Faktoren der verbleibenden Zahl zu finden. Diese Methode wird parallel auf mehreren Threads ausgeführt, um die Effizienz zu steigern.
5. Zusammenführen und Optimieren der Faktoren:
   Die gefundenen Faktoren werden in einer Liste gesammelt. Wenn mehrere Faktoren desselben Wertes gefunden wurden, werden sie zu einem einzigen Eintrag zusammengefasst und mit einer Zählung versehen, um die endgültige Darstellung der Primfaktoren zu erhalten.
6. Rückgabe des Ergebnisses:
   Das Programm gibt eine Struktur zurück, die Informationen über die Eingabezahl enthält, ob sie eine Primzahl ist, und die Liste der gefundenen Primfaktoren.

Quelltext von prime_factorization::Factorization:
https://docs.rs/prime_factorization/1.0.4/src/prime_factorization/factor/mod.rs.html

Cargo.toml

[package]
name = "primfaktorzerlegung"
version = "0.1.0"
edition = "2021"

[dependencies]
prime_factorization = "1.0.4"

main.rs

// Importieren der notwendigen Bibliotheken
use prime_factorization::Factorization;  // Import der Factorization-Struktur aus der externen Bibliothek prime_factorization
use std::env;  // Import der Umgebungsvariablen-Bibliothek
use std::time::Instant;  // Import der Zeitmessungs-Bibliothek

// Funktion zum Konvertieren einer Zahl in eine Zeichenkette mit hochgestellten Zahlen
fn zu_hochgestellt(zahl: u128) -> String {
    // Ein Array von hochgestellten Ziffern, die später verwendet werden
    let hochgestellte_ziffern: [&str; 10] =
        ["⁰", "¹", "²", "³", "⁴", "⁵", "⁶", "⁷", "⁸", "⁹"];

    let mut ergebnis = String::new();  // Eine leere Zeichenkette, um das Ergebnis zu speichern

    // Schleife durch jede Ziffer der Zahl
    for ziffer in zahl.to_string().chars() {
        let ziffernwert = ziffer.to_digit(10).unwrap_or(0) as usize;  // Wandelt die Ziffer in ihren numerischen Wert um
        ergebnis.push_str(hochgestellte_ziffern[ziffernwert]);  // Fügt die hochgestellte Ziffer zum Ergebnis hinzu
    }

    ergebnis  // Gibt das Ergebnis zurück
}

fn main() {
    // Überprüfen, ob ein Argument für die Zahl angegeben wurde
    let argumente: Vec<String> = env::args().collect();  // Ruft die Kommandozeilenargumente ab und speichert sie in einem Vektor
    if argumente.len() != 2 {  // Überprüft, ob genau ein Argument (die Zahl) angegeben wurde
        eprintln!("Bitte geben Sie eine 128-Bit-Zahl als Argument ein.");  // Gibt eine Fehlermeldung aus
        std::process::exit(1);  // Beendet das Programm mit einem Fehlercode
    }

    // Die Zahl aus dem ersten Argument parsen
    let zahl = match argumente[1].parse::<u128>() {
        Ok(n) if n >= 1 => n,  // Wandelt das Argument in eine u128-Zahl um, wenn es gültig ist und größer oder gleich 1 ist
        _ => {
            eprintln!("Ungültige oder nicht-positive Zahl eingegeben.");  // Gibt eine Fehlermeldung aus
            std::process::exit(1);  // Beendet das Programm mit einem Fehlercode
        }
    };

    // Zeitmessung starten
    let startzeit = Instant::now();  // Startet die Zeitmessung

    // Primfaktorzerlegung durchführen
    let faktor_repräsentation = Factorization::run(zahl);  // Ruft die Factorization-Funktion aus der Bibliothek auf

    // Zeitmessung beenden und Dauer in Millisekunden mit 3 Dezimalstellen berechnen
    let endzeit = startzeit.elapsed();  // Beendet die Zeitmessung
    let millisekunden_gesamt = endzeit.as_secs() * 1000 + u64::from(endzeit.subsec_millis());  // Berechnet die Gesamtdauer in Millisekunden
    let millisekunden_float = millisekunden_gesamt as f64 + f64::from(endzeit.subsec_micros()) / 1000.0;  // Konvertiert die Dauer in Gleitkommazahlen mit 3 Dezimalstellen

    // Ausgabe der Faktoren und Zeit auf 3 Stellen genau
    println!("Primfaktoren von {}:", zahl);  // Gibt eine Nachricht aus, welche Zahl zerlegt wird

    let mut faktoren_ausgabe = String::new();  // Eine leere Zeichenkette, um die Faktoren darin zu speichern
    let mut vorherige_primzahl: Option<u128> = None;  // Eine Option, um die vorherige Primzahl zu speichern
    let mut exponent = 1;  // Der Exponent für die aktuelle Primzahl, standardmäßig 1

    // Schleife durch die Primfaktoren
    for primzahl in faktor_repräsentation.factors.iter() {
        if Some(primzahl) == vorherige_primzahl.as_ref() {  // Überprüft, ob die aktuelle Primzahl gleich der vorherigen ist
            exponent += 1;  // Falls ja, erhöhe den Exponenten um 1
        } else {
            if !faktoren_ausgabe.is_empty() {
                faktoren_ausgabe.push_str(" × ");  // Falls die Ausgabe nicht leer ist, füge ein Multiplikationszeichen hinzu
            }
            if let Some(vorherige) = vorherige_primzahl {
                faktoren_ausgabe.push_str(&format!("{}{}", vorherige, if exponent > 1 { zu_hochgestellt(exponent) } else { "".to_string() }));  // Fügt die vorherige Primzahl zur Ausgabe hinzu
            }
            vorherige_primzahl = Some(*primzahl);  // Speichert die aktuelle Primzahl als vorherige Primzahl
            exponent = 1;  // Setzt den Exponenten auf 1 zurück
        }
    }

    if !faktoren_ausgabe.is_empty() {
        faktoren_ausgabe.push_str(" × ");  // Falls die Ausgabe nicht leer ist, füge ein Multiplikationszeichen hinzu
    }
    if let Some(vorherige) = vorherige_primzahl {
        faktoren_ausgabe.push_str(&format!("{}{}", vorherige, if exponent > 1 { zu_hochgestellt(exponent) } else { "".to_string() }));  // Fügt die letzte Primzahl zur Ausgabe hinzu
    }

    if faktoren_ausgabe.is_empty() {
        faktoren_ausgabe.push_str("1");  // Falls keine Faktoren gefunden wurden, füge "1" zur Ausgabe hinzu
    }

    println!("{}", faktoren_ausgabe);  // Gibt die Faktoren aus

    println!("Ist eine Primzahl: {}", faktor_repräsentation.is_prime);  // Gibt aus, ob die Zahl eine Primzahl ist
    println!("Programm benötigte {:.3} Millisekunden zur Ausführung.", millisekunden_float);  // Gibt die Ausführungsdauer aus

}

Siehe auch

https://docs.rs/prime_factorization Crate prime_factorization