Example - Counting Primes

There are at least two ways to do this problem. The first solution has a higher time complexity but a less complex implementation, while the second has a lower time complexity at the cost of a more complex implementation.

For a more complete explanation of these algorithms, refer to this CF blog post.

Explanation 1

Utilizes a dynamic programming approach based on a recursion relation derived from sieving.

The algorithm iteratively reduces the count of numbers that are not divisible by primes, utilizing a recursive formula. It achieves a complexity of $O(\frac{N^{3/4}}{\sqrt{\log N}})$.

Implementation

Time Complexity: $O(\frac{N^{3/4}}{\sqrt{\log N}})$

Copy
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

using ll = long long;
using std::cout;
using std::endl;
using std::pair;
using std::vector;

Explanation 2

There exists an $O(\frac{n^{2/3}}{\sqrt[3]{\log n}})$ implementation; see Maksim1744’s Codeforces blog for more details. Below is an implementation with a BIT. Note that the fastest solutions to this library checker problem look like they run in $O(\frac{N^{3/4}}{\sqrt{\log N}})$.

Implementation

Time Complexity: $O(\frac{n^{2/3}}{\sqrt[3]{\log n}})$

Copy
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

using ll = long long;
using std::cout;
using std::endl;
using std::pair;
using std::vector;

Problems