Rust エラトステネスのふるい

バージョン

• rustc 1.45.0-nightly

依存クレート

[dependencies]
text_io = "=0.1.8"

コード

use text_io::read;

fn main() {
    let x: usize = read!();
    let mut flags = vec![true; x + 1];
    flags[0] = false;
    flags[1] = false;
    let sqrt_x = (f64::sqrt(x as f64) + 0.1).ceil() as usize;
    for p in 2..=sqrt_x {
        if !flags[p] {
            continue;
        }
        for mult in ((p*p)..=x).step_by(p) {
            flags[mult] = false;
        }
    }

    for (i, v) in flags.iter().enumerate() {
        if *v {
            print!("{} ", i);
        }
    }
}

入出力

例えば 100 と入力すると

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

を出力する。

参考

https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
https://qiita.com/peria/items/a4ff4ddb3336f7b81d50