Struct nekolib::math::LinearSieve

source ·
pub struct LinearSieve { /* private fields */ }
Expand description

線形篩。

Idea

各整数の最小素因数を求めつつ、素数のリストを作成していく。

$\gdef\lpf#1{\operatorname{lpf}(#1)}$ $i$ の最小素因数を $\mathrm{lpf}(i)$ と書く。$j \le \lpf{i}$ なる各素数 $j$ に対して、$\lpf{i\times j} = j$ とわかる。 素因数分解の一意性から、各整数の最小素因数の更新は一回ずつしか行われず、線形時間で構築できる。

また、$\lpf{i}$ が $\lpf{i / \lpf{i}}$ と等しいかで場合分けしながら DP することで、各 $i$ が $\lpf{i}$ で何回割り切れるかも求められる。 なお、これは DP せず各 $i$ に対して愚直に計算しても $O(n)$ になることが示せるらしい。

Complexity

演算時間計算量
new$\Theta(n)$
is_prime$\Theta(1)$
least_factor$\Theta(1)$
factors_dup$\Theta(1)$ delay
factors$\Theta(1)$ delay
euler_phi$\Theta(\omega(n))$
euler_phi_star$O(\omega(n)\log(n))$
divisors$O(\sigma(n))$
divisors_count$O(\omega(n))$
divisors_sum$O(\omega(n))$
primes$\Theta(1)$ delay
recips$O(n)$

$n$ の素因数の個数を $\omega(n)$ とすると、以下の式が成り立つらしい。 $$ \sum_{i\le n} \omega(i) = n\ln(\ln(n)) + O(n). $$

また、$n$ 以下の素数の個数を $\pi(n)$ とすると、以下の式が成り立つ(素数定理)。 $$ \pi(n) = \frac{n}{\ln(n)} + O{\left(\frac{n}{\ln(n)^2}\right)}. $$

Examples

use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert!(!sieve.is_prime(1));
assert!(sieve.is_prime(2));
assert!(sieve.is_prime(23));
assert!(!sieve.is_prime(24));

assert_eq!(sieve.least_factor(1), None);
assert_eq!(sieve.least_factor(3), Some(3));
assert_eq!(sieve.least_factor(24), Some(2));

assert_eq!(sieve.factors_dup(1).next(), None);
assert_eq!(sieve.factors_dup(60).collect::<Vec<_>>(), vec![2, 2, 3, 5]);

assert_eq!(
    sieve.primes().take(10).collect::<Vec<_>>(),
    vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
);

References

Implementations§

$n$ 以下の自然数に対する篩を用意する。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);

$n$ が素数であれば true を返す。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert!(!sieve.is_prime(1));
assert!(sieve.is_prime(2));
assert!(sieve.is_prime(23));
assert!(!sieve.is_prime(24));

$n$ の最小素因数を返す。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert_eq!(sieve.least_factor(1), None);
assert_eq!(sieve.least_factor(3), Some(3));
assert_eq!(sieve.least_factor(24), Some(2));

$n$ の素因数を列挙する。重複あり。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert_eq!(sieve.factors_dup(1).next(), None);
assert_eq!(sieve.factors_dup(60).collect::<Vec<_>>(), vec![2, 2, 3, 5]);

$n$ を素因数分解する。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert_eq!(sieve.factors(1).next(), None);
assert_eq!(
    sieve.factors(60).collect::<Vec<_>>(),
    vec![(2, 2), (3, 1), (5, 1)]
);

$\phi(n)$ を求める。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert_eq!(sieve.euler_phi(1), 1);
assert_eq!(sieve.euler_phi(35), 24);
assert_eq!(sieve.euler_phi(60), 16);

$\phi^\star(n)$ を求める。

$n$ に $\phi$ を繰り返し適用して $1$ にするために必要な最小回数である。 $n\gt 1$ に対して $\phi(\phi(n)) \le n/2$ なので、 $\phi^\star(n) = O(\log(n))$ である。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert_eq!(sieve.euler_phi_star(1), 0);
assert_eq!(sieve.euler_phi_star(35), 5);
assert_eq!(sieve.euler_phi_star(60), 5);

assert_eq!(sieve.euler_phi(35), 24);
assert_eq!(sieve.euler_phi(24), 8);
assert_eq!(sieve.euler_phi(8), 4);
assert_eq!(sieve.euler_phi(4), 2);
assert_eq!(sieve.euler_phi(2), 1);

assert_eq!(sieve.euler_phi(60), 16);
assert_eq!(sieve.euler_phi(16), 8);

$n$ の約数を列挙する。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert_eq!(sieve.divisors(1).next(), Some(1));
assert_eq!(sieve.divisors(1).nth(1), None);
assert_eq!(
    sieve.divisors(60).collect::<Vec<_>>(),
    vec![1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
);

$n$ の約数の個数を返す。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert_eq!(sieve.divisors_count(1), 1);
assert_eq!(sieve.divisors_count(60), sieve.divisors(60).count());

$n$ の約数の総和を返す。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert_eq!(sieve.divisors_sum(1), 1);
assert_eq!(sieve.divisors_sum(8), 15);
assert_eq!(sieve.divisors_sum(60), 168);

素数を列挙する。

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert_eq!(
    sieve.primes().take(10).collect::<Vec<_>>(),
    vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
);

法 $m$ での逆元を返す。

$\gdef\recip#1#2{#1^{-1}_{(#2)}}$ $i^{-1}\bmod j$ を $\recip{i}{j}$ と書く。 次で定められる $a = (a_0, a_1, \dots, a_n)$ を返す。 $$ a_i = \begin{cases} \recip{i}{m}, & \text{if }\recip{i}{m}\text{ exists}; \\ 0, & \text{otherwise}. \end{cases} $$ Note: $\recip{i}{m}\ne 0$。

Idea

$$ \recip{i}{m} \equiv \recip{\lpf{i}}{m}\cdot\recip{(i/\lpf{i})}{m}\pmod{m} $$ に基づく。素数は $O(n/\log(n))$ 個しかないため、互除法で愚直に求めても全体では $O(n)$ 時間となる。

See also

https://37zigen.com/linear-sieve/#i-4

Examples
use nekolib::math::LinearSieve;

let sieve = LinearSieve::new(60);
assert_eq!(sieve.recips(0, 1), [0]);
assert_eq!(sieve.recips(4, 5), [0, 1, 3, 2, 4]);
assert_eq!(sieve.recips(9, 10), [0, 1, 0, 7, 0, 0, 0, 3, 0, 9]);

Auto Trait Implementations§

Blanket Implementations§

Gets the TypeId of self. Read more
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.