リュカ・レーマーテストの実装

lucas.rs

use rug::{ops::Pow, Integer};

struct PrimeNumber {
    num: Integer,
    is_prime: bool,
}

fn lucas_lehmer_test(p: u32) -> PrimeNumber {
    // Mercenne Number : (2^p - 1)
    let mersenne_number = |v| (Integer::from(1) << v) - 1;
    let m = mersenne_number(p);
    let mut s = Integer::from(4); // s_0 = 4
    for _ in 2..p {
        s = (s.pow(2) - 2) % &m;
    }

    let pn = PrimeNumber {
        num: m,
        is_prime: s == 0,
    };
    return pn;
}

fn main() {
    // 100 以下の奇数の素数
    let p_list = [
        3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
    ];

    let mut count = 0;
    let mut perfect_num;
    for p in p_list {
        let n = lucas_lehmer_test(p);
        if n.is_prime {
            let v = n.num;
            let ref k = &v;
            perfect_num = *k * Integer::from(1) << (p - 1);
            println!(
                "[p = {}] {} is prime number / also {} is perfect number",
                p, *k, perfect_num
            );
            count += 1;
        } else {
            println!("[p = {}] {} is composite number", p, n.num);
        }
    }
    println!("number of Mersenne primes (p<100) : {}", count + 1);
}

/*
output:
[p = 3] 7 is prime number / also 28 is perfect number
[p = 5] 31 is prime number / also 496 is perfect number
[p = 7] 127 is prime number / also 8128 is perfect number
[p = 11] 2047 is composite number
[p = 13] 8191 is prime number / also 33550336 is perfect number
[p = 17] 131071 is prime number / also 8589869056 is perfect number
[p = 19] 524287 is prime number / also 137438691328 is perfect number
[p = 23] 8388607 is composite number
[p = 29] 536870911 is composite number
[p = 31] 2147483647 is prime number / also 2305843008139952128 is perfect number
[p = 37] 137438953471 is composite number
[p = 41] 2199023255551 is composite number
[p = 43] 8796093022207 is composite number
[p = 47] 140737488355327 is composite number
[p = 53] 9007199254740991 is composite number
[p = 59] 576460752303423487 is composite number
[p = 61] 2305843009213693951 is prime number / also 2658455991569831744654692615953842176 is perfect number
[p = 67] 147573952589676412927 is composite number
[p = 71] 2361183241434822606847 is composite number
[p = 73] 9444732965739290427391 is composite number
[p = 79] 604462909807314587353087 is composite number
[p = 83] 9671406556917033397649407 is composite number
[p = 89] 618970019642690137449562111 is prime number / also 191561942608236107294793378084303638130997321548169216 is perfect number
[p = 97] 158456325028528675187087900671 is composite number
number of Mersenne primes (under 100) : 10
*/