PrevNext
Has Not Appeared

Prefix Sums of Multiplicative Functions

Author: Benjamin Qi

?

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

1template<int SZ> struct Sieve {
2 vi pr;
3 int sp[SZ], phi[SZ]; // smallest prime that divides
4 Sieve() { // above is faster
5 memset(sp,0,sizeof sp);
6 phi[1] = 1;
7 FOR(i,2,SZ) {
8 if (sp[i] == 0) {
9 sp[i] = i, pr.pb(i); phi[i] = i-1;
10 } trav(p,pr) {

(project euler)

(topcoder problem)

Module Progress:

Give Us Feedback on Prefix Sums of Multiplicative Functions!

PrevNext