Struct nekolib::math::SieveN2PlusNPlus1

pub struct SieveN2PlusNPlus1 { /* private fields */ }

$n^2+n+1$ 型素数の篩。

Idea

todo!()

References

• https://inamori.hateblo.jp/entry/20110930/p1

Implementations

impl SieveN2PlusNPlus1

pub fn new(n: usize) -> Self

初期化する。

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

$n^2+n+1$ の形の素数を返す。

Examples

use nekolib::math::SieveN2PlusNPlus1;

let ss = SieveN2PlusNPlus1::new(10);
let primes: Vec<_> = ss.primes().collect();
assert_eq!(primes, [3, 7, 13, 31, 43, 73]);

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

$n^2+n+1$ が素数のとき真を返す。

Examples

use nekolib::math::SieveN2PlusNPlus1;

let ss = SieveN2PlusNPlus1::new(10);
assert!(ss.is_prime(3));  // 13 is prime
assert!(!ss.is_prime(4));  // 21 = 3 * 7

pub fn factors(&self, n: usize) -> impl Iterator<Item = (usize, u32)> + '_

$n^2+n+1$ を素因数分解する。

底の昇順とは限らないので注意。

Examples

use nekolib::math::SieveN2PlusNPlus1;

let ss = SieveN2PlusNPlus1::new(20);
assert_eq!(ss.factors(0).next(), None);
assert_eq!(ss.factors(7).collect::<Vec<_>>(), [(3, 1), (19, 1)]);
assert_eq!(ss.factors(18).collect::<Vec<_>>(), [(7, 3)]);

pub fn factors_dup(&self, n: usize) -> impl Iterator<Item = usize> + '_

$n^2+1$ を素因数を列挙する。重複あり。

底の昇順とは限らないので注意。

Examples

use nekolib::math::SieveN2PlusNPlus1;

let ss = SieveN2PlusNPlus1::new(20);
assert_eq!(ss.factors_dup(0).next(), None);
assert_eq!(ss.factors_dup(6).collect::<Vec<_>>(), [43]);
assert_eq!(ss.factors_dup(18).collect::<Vec<_>>(), [7, 7, 7]);

Trait Implementations

impl Clone for SieveN2PlusNPlus1

fn clone(&self) -> SieveN2PlusNPlus1

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for SieveN2PlusNPlus1

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

Formats the value using the given formatter.