シクシク素数列 Advent Calendar 2018 (Rust)

Rust で書いたよ

use std::io::stdin;

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

fn is_4949(mut n: u128) -> bool {
    loop {
        if n == 0 {
            return false;
        }
        match n % 10 {
            4 | 9 => return true,
            _ => n /= 10,
        }
    }
}

fn solve_4949(n: usize) -> Vec<u128> {
    let mut ans = Vec::new();
    let mut i = 1;
    while ans.len() < n {
        if is_prime(i) && is_4949(i) {
            ans.push(i);
        }
        i += 1;
    }
    ans
}

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let n = buf.trim().parse().expect("fail parse as integer");
    let ans = solve_4949(n);
    println!(
        "{}",
        ans.iter()
            .map(|n| n.to_string())
            .collect::<Vec<String>>()
            .join(","),
    );
}

#[test]
fn test_prime() {
    assert_eq!(is_prime(0), false);
    assert_eq!(is_prime(1), false);
    assert_eq!(is_prime(2), true);
    assert_eq!(is_prime(57), false);
    assert_eq!(is_prime(97), true);
}

#[test]
fn test_4949() {
    assert_eq!(is_4949(0), false);
    assert_eq!(is_4949(1), false);
    assert_eq!(is_4949(4), true);
    assert_eq!(is_4949(9), true);
    assert_eq!(is_4949(87318112), false);
    assert_eq!(is_4949(987318112), true);
}

cargo で動かすよ

$ cargo test
   Compiling qiita4949 v0.1.0 (./qiita4949)
    Finished dev [unoptimized + debuginfo] target(s) in 1.33s
     Running target/debug/deps/qiita4949-5b899812a8ccb542

running 2 tests
test test_4949 ... ok
test test_prime ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

$ cargo build --release 
   Compiling qiita4949 v0.1.0 (./qiita4949)
    Finished release [optimized] target(s) in 0.47s
$ echo 9 | ./target/release/qiita4949 
19,29,41,43,47,59,79,89,97
$ echo 100 | ./target/release/qiita4949
19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319

$ echo 10000 | time ./target/release/qiita4949 > /dev/null
       20.19 real        20.16 user         0.01 sys

遅い
（アルゴリズムが悪い）