【Rust】素数の無限リスト【整数論】

  • 2021年12月26日
  • 2022年8月1日
  • Rust
  • 143View
  • 0件

はじめに

Rust で素数の無限リスト生成を実装します。

素数とは、2以上の自然数で、他の数字で割り切ることができないような数を表します。
ジェネレータクラスに Iterator Trait を実装することで、無限リストの生成を実現します。

Wikipedia 素数

サンプルコード

無限の素数リスト生成

サンプルコードです。
10番目、1000番目、10000番目の素数を出力しました。

struct PrimeNumberGenerator {
    next: u32,
    ps: Vec<u32>,
}
impl Iterator for PrimeNumberGenerator {
    type Item = u32;
    fn next(&mut self) -> Option<Self::Item> {
        let mut curr = self.next;
        while is_divisible_any(curr, &self.ps) {
            curr += 1;
        }
        self.next = curr + 1;
        self.ps.push(curr);
        Some(curr)
    }
}
fn is_divisible_any(n: u32, ps: &Vec<u32>) -> bool {
    ps.iter().take_while(|&p| p * p <= n).any(|p| n % p == 0)
}
fn prime_numbers() -> PrimeNumberGenerator {
    PrimeNumberGenerator {
        next: 2,
        ps: vec![],
    }
}
fn main() {
    println!("{:?}", prime_numbers().take(10).collect::<Vec<_>>());
    println!("{:?}", prime_numbers().nth(9));
    println!("{:?}", prime_numbers().nth(999));
    println!("{:?}", prime_numbers().nth(9_999));
}
❯ rustc main.rs && ./main
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Some(29)
Some(7919)
Some(104729)

おしまい!