Prefix Sums of Multiplicative Functions

https://codeforces.com/blog/entry/54150

Linear Time Sieve

https://judge.yosupo.jp/problem/enumerate_primes

Counting Primes

https://judge.yosupo.jp/problem/counting_primes

Totient Function

https://judge.yosupo.jp/problem/sum_of_totient_function

Copy
template <int SZ> struct Sieve {
	vi pr;
	int sp[SZ], phi[SZ];  // smallest prime that divides
	Sieve() {             // above is faster
		memset(sp, 0, sizeof sp);
		phi[1] = 1;
		FOR(i, 2, SZ) {
			if (sp[i] == 0) {
				sp[i] = i, pr.pb(i);
				phi[i] = i - 1;

(project euler)

(topcoder problem)