library_checker/number_theory/counting_primes.rs
1use competitive::prelude::*;
2use competitive::{algebra::AdditiveOperation, math::QuotientArray};
3
4#[verify::library_checker("counting_primes")]
5pub fn counting_primes(reader: impl Read, writer: impl Write) {
6 prepare_io!(reader, writer);
7 sc!(n: u64);
8 let qa = QuotientArray::from_fn(n, |i| i as i64 - 1).lucy_dp::<AdditiveOperation<_>>(|x, _p| x);
9 pp!(qa[n]);
10}