書き初め@2017

miller_rabin.rs

fn is_prime(n: u64) -> bool {
    return miller_rabin_test(n,
                             [2, 325, 9375, 28178, 450775, 9780504, 1795265022]);
}

fn miller_rabin_test(n: u64, bases: [u64; 7]) -> bool {
    match n {
        0 | 1 => return false,
        2 | 3 => return true,
        n if n & 1 == 0 => return false,
        n => {
            let mut d =  n-1;
            while d & 1 == 0 {
                d >>= 1 ;
            }
            for base in bases.iter() {
                let mut t = d;
                let mut y = mod_pow(*base, t, n);
                while t != n-1 &&  y != 1 && y != n-1 {
                    y = ( y * y ) % n;
                    t <<= 1;
                }
                if y != n-1 && t & 1 == 0 {
                    return false ;
                }
            }
            return true;
        }
    }
}

fn mod_pow(base: u64, pow: u64, modulo: u64) -> u64{
    let mut result = 1;
    let mut b = base;
    let mut p = pow;
    while p > 0 {
        if p & 1 == 1 {
            result = ( result * b ) % modulo;
        }
        b = (b * b) % modulo;
        p >>= 1;
    }
    return result;
}

fn main() {
    let new_year = 2017;
    if is_prime(new_year) {
        println!("{} is prime year!", new_year);
    } else {
        println!("{} is not prime year...", new_year);
    }
}

ミラー–ラビン素数判定法 - Wikipediaと
Deterministic variants of the Miller-Rabin primality test. Miller-Rabin SPRP bases recordsを参考にした

2017 is prime year!