library_checker/math/
counting_primes.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{algebra::AdditiveOperation, math::QuotientArray};
4
5#[verify::library_checker("counting_primes")]
6pub fn counting_primes(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n: u64);
10    let qa = QuotientArray::from_fn(n, |i| i as i64 - 1).lucy_dp::<AdditiveOperation<_>>(|x, _p| x);
11    writeln!(writer, "{}", qa[n]).ok();
12}