5
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

シクシク素数列Advent Calendar 2018

Day 9

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

Last updated at Posted at 2018-12-08

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

遅い :cry:
(アルゴリズムが悪い)

5
0
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?