This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
// F is called for each prime // Sieve (odd only + segmented) {{{ template<typename F> void sieve(int MAX, F func) { const int S = sqrt(MAX + 0.5); vector<char> sieve(S + 1, true); vector<array<int, 2>> cp; for (int i = 3; i <= S; i += 2) { if (!sieve[i]) continue; cp.push_back({i, (i * i - 1) / 2}); for (int j = i * i; j <= S; j += 2 * i) sieve[j] = false; } func(2); vector<char> block(S); int high = (MAX - 1) / 2; for (int low = 0; low <= high; low += S) { fill(block.begin(), block.end(), true); for (auto &i : cp) { int p = i[0], idx = i[1]; for (; idx < S; idx += p) block[idx] = false; i[1] = idx - S; } if (low == 0) block[0] = false; for (int i = 0; i < S && low + i <= high; i++) if (block[i]) { func((low + i) * 2 + 1); } }; } // }}}
#line 1 "Math/Prime/Sieve.h" // F is called for each prime // Sieve (odd only + segmented) {{{ template<typename F> void sieve(int MAX, F func) { const int S = sqrt(MAX + 0.5); vector<char> sieve(S + 1, true); vector<array<int, 2>> cp; for (int i = 3; i <= S; i += 2) { if (!sieve[i]) continue; cp.push_back({i, (i * i - 1) / 2}); for (int j = i * i; j <= S; j += 2 * i) sieve[j] = false; } func(2); vector<char> block(S); int high = (MAX - 1) / 2; for (int low = 0; low <= high; low += S) { fill(block.begin(), block.end(), true); for (auto &i : cp) { int p = i[0], idx = i[1]; for (; idx < S; idx += p) block[idx] = false; i[1] = idx - S; } if (low == 0) block[0] = false; for (int i = 0; i < S && low + i <= high; i++) if (block[i]) { func((low + i) * 2 + 1); } }; } // }}}