↑Programmieren in Rust

Algorithmen: Zahlentheorie

Inhaltsverzeichnis

1. Größter gemeinsamer Teiler
2. Kleinstes gemeinsames Vielfaches
3. Modulare Potenzfunktion
4. Primzahlen
5. Teiler
6. Eulersche Phi-Funktion

Größter gemeinsamer Teiler

// Klassischer euklidischer Algorithmus, rekursiv
fn gcd(a: u32, b: u32) -> u32 {
         if b == 0 {a}
    else if a == 0 {b}
    else if b < a {gcd(a - b, b)}
    else {gcd(a, b - a)}
}

// Klassischer euklidischer Algorithmus, iterativ
fn gcd(mut a: u32, mut b: u32) -> u32 {
    if a == 0 {b}
    else {
        while b != 0 {
            if b < a {a = a - b;} else {b = b - a;}
        }
        a
    }
}

// Moderner euklidischer Algorithmus, rekursiv
fn gcd(a: u32, b: u32) -> u32 {
    if b == 0 {a} else {gcd(b, a%b)}
}

// Moderner euklidischer Algorithmus, iterativ
// ("Turbo-Euklid")
fn gcd(mut a: u32, mut b: u32) -> u32 {
    while b != 0 {
        let h = a%b;
        a = b; b = h;
    }
    a
}

Kleinstes gemeinsames Vielfaches

fn lcm(a: u32, b: u32) -> u32 {
    a*b/gcd(a, b)
}

fn lcm_slice(a: &[u32]) -> u32 {
    a.iter().fold(1, |a, &b| {a*b/gcd(a, b)})
}

Modulare Potenzfunktion

Ohne Überlauf-Prüfung

fn pow_mod(mut x: u32, mut n: u32, m: u32) -> u32 {
    let mut y: u32 = 1;
    while n > 1 {
        if n%2 == 1 {y = (y*x)%m;}
        n /= 2; x = (x*x)%m;
    }
    if n == 1 {y = (y*x)%m;}
    y
}

Mit Überlauf-Prüfung

fn pow_mod(mut x: u32, mut n: u32, m: u32) -> Option<u32> {
    let mut y: u32 = 1;
    while n > 1 {
        if n%2 == 1 {y = y.checked_mul(x)?%m;}
        n /= 2; x = x.checked_mul(x)?%m;
    }
    if n == 1 {y = y.checked_mul(x)?%m;}
    Some(y)
}

Primzahlen

Naiver Primzahltest

fn is_prime(n: u64) -> bool {
    (1..n+1).filter(|i| n%i == 0).count() == 2
}

fn is_prime(n: u64) -> bool {
    for i in 2..n {
        if n%i == 0 {return false;}
    }
    true
}

Verbesserter Primzahltest

fn is_prime(n: u64) -> bool {
    let mut i: u64 = 2;
    while i*i <= n {
        if n%i == 0 {return false;}
        i += 1;
    }
    true
}

Schneller Primzahltest

fn is_prime_trial_div(n: u32) -> bool {
    if n < 4 {return n > 1;}
    if n%2 == 0 || n%3 == 0 {return false;}
    let mut i = 5;
    let mut w = 2;
    while i*i <= n {
        if n%i == 0 {return false;}
        i += w;
        w = 6 - w;
    }
    true
}

fn pow_mod(a: u32, mut n: u32, m: u32) -> u64 {
    let mut p: u64 = 1;
    let mut a: u64 = u64::from(a%m);
    while n > 1 {
        if n&1 == 1 {p = (p*a)%u64::from(m);}
        n >>= 1; a = (a*a)%u64::from(m);
    }
    if n == 1 {p = (p*a)%u64::from(m);}
    p
}

fn witness(a: u32, d: u32, n: u32, mut r: u32) -> bool {
    let mut p = pow_mod(a, d, n);
    if p == 1 {
        true
    } else {
        while r != 0 {
            if p == u64::from(n-1) {return true;}
            p = (p*p)%u64::from(n);
            r -= 1;
        }
        false
    }
}

pub fn is_prime(n: u32) -> bool {
    if n < 13000000 {
        return is_prime_trial_div(n);
    } else if n&1 == 0 {
        return false;
    }

    // let (2^r)*d = n - 1;
    let mut r = 0;
    let mut d = n - 1;
    while d&1 == 0 {r += 1; d >>= 1;}

    // Miller-Rabin-Test
    [2, 7, 61].iter().all(|&a| witness(a, d, n, r))
}

Primfaktorzerlegung

fn factor(mut n: u64) -> Vec<(u64, u8)> {
    let mut acc: Vec<(u64, u8)> = vec![];
    let mut p = 2;
    while p <= n {
        let mut k = 0;
        while n%p == 0 {n = n/p; k += 1;}
        if k != 0 {acc.push((p, k));}
        p += 1;
    }
    acc
}

Teiler

// Teilerliste
fn divisors(n: u64) -> Vec<u64> {
    (1..n+1).filter(|i| n%i == 0).collect()
}

// Teileranzahlfunktion
fn sigma0(n: u64) -> usize {
    (1..n+1).filter(|i| n%i == 0).count()
}

// Teilerfunktion
fn sigma(x: u32, n: u64) -> u64 {
    (1..n+1).filter(|i| n%i == 0).map(|i| i.pow(x)).sum()
}

Eulersche Phi-Funktion

fn phi(mut n: u32) -> u32 {
    if n == 0 {return 0;}
    let mut y: u32 = 1;
    let mut p = 2;
    while p <= n {
        let mut k = 0;
        while n%p == 0 {n = n/p; k += 1;}
        if k != 0 {y *= p.pow(k-1)*(p-1);}
        p += 1;
    }
    y
}