Struct Sieve 

pub struct Sieve { /* private fields */ }

エラトステネスの篩で素数と最小素因数を前計算します。

0..=limit の範囲で素数判定と素因数分解を行うため、各整数の最小素因数を保持します。 is_prime は O(1)、prime_factorize は素因数の重複度（指数の合計）に比例する O(log n) 時間で計算できます。素数列挙は primes() から行えます。

構築の計算量は O(N log log N)、使用メモリは O(N) です。

Examples

use atcoder::math::sieve::Sieve;

let sieve = Sieve::new(100);

assert!(sieve.is_prime(97));
assert!(!sieve.is_prime(1));

assert_eq!(
    sieve.prime_factorize(84),
    vec![(2, 2), (3, 1), (7, 1)],
);

Implementations

impl Sieve

pub fn new(limit: usize) -> Self

0..=limit の各整数について最小素因数を前計算します。判定・分解可能な値はこの範囲内です。

計算量は O(limit log log limit)、使用メモリは O(limit) です。

pub fn limit(&self) -> usize

前計算した範囲の上端 limit を返します（有効範囲は 0..=limit()）。

pub fn is_prime(&self, n: usize) -> bool

前計算範囲内の n が素数かどうかを返します。0 と 1 は false です。

計算量は O(1) です。

Panics

n > limit の場合は panic します。

pub fn primes(&self) -> impl Iterator<Item = usize> + '_

0..=limit() に含まれる素数を昇順に列挙します。

全要素を列挙する計算量は O(limit()) です。イテレータは self を借用するため、 Sieve より長く保持することはできません。

pub fn prime_factorize(&self, n: usize) -> Vec<(usize, usize)>

前計算範囲内の n を素因数分解し、(素因数, 指数) の組を素因数の昇順で返します。

n = 1 の場合は空の Vec を返します。n = 0 は素因数分解できません。 計算量は素因数の重複度を含めて O(log n) です。

Panics

• n = 0 の場合
• n > limit の場合

Trait Implementations

impl Clone for Sieve

fn clone(&self) -> Sieve

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Sieve

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.