### potter's blog

By potter, history, 7 months ago,

I have tried sieve and segmented sieve too but they are slow. Can anyone provide code to print primes till 10^9 FAST?

Python code would be a great help.

• -17

 » 7 months ago, # |   0
•  » » 7 months ago, # ^ |   -16 Can you share the same for python?
 » 7 months ago, # | ← Rev. 3 →   +3 AFAIK, just using sieve to count prime upto 1e9 is already 600ms for fasted code I known (run on GNU G++17 7.3.0 CF 23/9/2021). Taking all primes $\leq 10^9$ is already 4-5 seconds ($50,847,534$ numbers). Assuming your " FAST " mean 1 second then I would like to say it must be very heavily micro-optimized for each operation to do so.But enumerate through all prime $\leq 10^9$ under 1 second is possible if you manage to maintain the prime array for each range
•  » » 7 months ago, # ^ |   0 Then how to solve those primes questions with limited time constraints. I don't remember the question now but I have encountered some of them , where I always got the TLE. How do I solve those?Sorry for not having perfect question right now. Its just that I came across many primes one, and couldn't solve any of it. So I am learning about all this.
•  » » 7 months ago, # ^ |   0 600ms seems quite fast if the sieve is actually generating all of the primes in that range and not using number theory magic to count them in $o(n)$. Care to share? I tried writing a somewhat optimized segmented sieve in Haskell in response to this blog's now-deleted predecessor, getting generation down to about 1.7 seconds and generation+printing down to about 2.8 seconds. My code seemed to get mangled when I tried to insert it into this comment (probably due its use of \$ interacting poorly with MathJax), so here it as a submission link: 141417208. The quoted times above are from Custom Invocation with input 1000000000 240000 1200.I estimate the printing alone would take about 2 seconds, and I'm not aware of any integer output template in any language that's appreciably faster than the one I use in my Haskell code, so 1 second for generation+printing might be infeasible. But obviously an un-fused lazy singly-linked list is not a very efficient data structure to hold 50 million Ints in (it would be over 2GB if it existed in memory all at once...), and I don't think GHC is very good at optimizing this kind of array-heavy code, so maybe it's possible to actually generate the primes a good deal faster than I do.
•  » » » 7 months ago, # ^ |   +8 Well I just use my own modified version from Bitwise Segment Sieve from prime sieve github (which some bitwise wheel sieve precalculation) that specifically sieve for int $\leq 10^9$. If just to count number then it is fast but if to collect all prime numbers then it is much slower than Non-bitwise one.The code 23 and 24 are lost during the covid but I think it still being saved somewhere in my old computer. Yet I will try to remake a new one if possible. The blog I am writing is not completed, but you can see the code1 - Brute-forces#include using namespace std; const int LIM = 1e6; bool checkPrime(int n) { int cnt = 0; for (int d = 1; d <= n; ++d) if (n % d == 0) ++cnt; return cnt == 2; } int cntPrime; bool isPrime[LIM + 1]; void sieve(int n) { cntPrime = 0; for (int x = 0; x <= n; ++x) { if (checkPrime(x)) { ++cntPrime; isPrime[x] = true; } } } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  2.Trial Division#include using namespace std; const int LIM = 1e6; bool checkPrime(int n) { if (n <= 1) return false; for (int d = 2; d * d <= n; ++d) if (n % d == 0) return false; return true; } int cntPrime; bool isPrime[LIM + 1]; void sieve(int n) { cntPrime = 0; for (int x = 0; x <= n; ++x) { if (checkPrime(x)) { ++cntPrime; isPrime[x] = true; } } } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  3.Improved Trial Division#include #include using namespace std; const int LIM = 1e6; bool checkPrime(int n) { if (n <= 1) return false; if (n == 2 || n == 3 || n == 5) return true; if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false; for (int d = 5; d * d <= n; d += 6) { if (n % d == 0) return false; if (n % (d + 2) == 0) return false; } return true; } int cntPrime; bool isPrime[LIM + 1]; void sieve(int n) { memset(isPrime, false, sizeof(isPrime)); isPrime[2] = isPrime[3] = true; cntPrime = (n >= 2) + (n >= 3); for (int x = 5; x <= n; x += 6) { if (checkPrime(x)) { ++cntPrime; isPrime[x] = true; } if (checkPrime(x + 2)) { ++cntPrime; isPrime[x + 2] = true; } } } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  4.Second Improved Trial Division#include #include #include #include using namespace std; typedef unsigned int uint; const int LIM = 1e6; int cntPrime; int prime[LIM + 1]; void sieve(int n) { cntPrime = 0; if (n < 2) return ; prime[cntPrime++] = 2; if (n < 3) return ; prime[cntPrime++] = 3; int sqrtn = 3, tickn = 1; for (int x = 5, t = 1; x <= n; x += 2 + 2 * (t ^= 1)) { bool ok = true; for (int i = 0; i < cntPrime && prime[i] <= sqrtn; ++i) { if (x % prime[i] == 0) { ok = false; break; } } if (ok) prime[cntPrime++] = x; if (--tickn == 0) tickn = sqrtn++; if (t && --tickn == 0) tickn = sqrtn++; } } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  5.Divisor Sieve#include #include using namespace std; const int LIM = 1e6; int cntPrime; bool isPrime[LIM + 1]; void sieve(int n) { memset(isPrime, true, sizeof(isPrime[0]) * (n + 1)); isPrime[0] = isPrime[1] = false; for (int p = 2; p * p <= n; ++p) for (int v = 2; p * v <= n; ++v) isPrime[p * v] = false; cntPrime = 0; for (int p = 0; p <= n; ++p) cntPrime += isPrime[p]; } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  6.Sundaram Sieve#include #include using namespace std; const int LIM = 1e6; int cntPrime; bool isPrime[LIM / 2 + 1]; void sieve(int n) { int k = (n - 2) / 2; memset(isPrime, true, sizeof(isPrime[0]) * (k + 1)); isPrime[0] = false; for (int i = 1; i * i <= n; ++i) for (int j = i; i + j + 2 * i * j <= k; ++j) isPrime[i + j + 2 * i * j] = false; cntPrime = 1; for (int i = 1; i <= k; ++i) if (isPrime[i] == true) /// prime 2 * i + 1 ++cntPrime; } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  7.Eratosthenes Sieve#include #include using namespace std; const int LIM = 1e6; int cntPrime; bool isPrime[LIM + 1]; void sieve(int n) { memset(isPrime, true, sizeof(isPrime[0]) * (n + 1)); isPrime[0] = isPrime[1] = false; for (int p = 2; p * p <= n; ++p) if (isPrime[p]) for (int x = p + p; x <= n; x += p) isPrime[x] = false; cntPrime = 0; for (int p = 0; p <= n; ++p) cntPrime += isPrime[p]; } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  8.Improved Eratosthenes Sieve#include #include using namespace std; const int LIM = 1e6; int cntPrime; bool isPrime[LIM + 1]; void sieve(int n) { memset(isPrime, true, sizeof(isPrime[0]) * (n + 1)); isPrime[0] = isPrime[1] = false; for (int p = 4; p <= n; p += 2) isPrime[p] = false; for (int p = 3; p * p <= n; p += 2) if (isPrime[p]) for (int x = p * p; x <= n; x += p) isPrime[x] = false; cntPrime = (n >= 2); for (int p = 3; p <= n; p += 2) cntPrime += isPrime[p]; } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  9.Linear Eratosthenes Sieve#include #include using namespace std; const int LIM = 1e6; vector prime; vector lpf; void sieve(int n) { prime.assign(1, 2); lpf.assign(n + 1, 2); for (int x = 3; x <= n; x += 2) { if (lpf[x] == 2) prime.push_back(lpf[x] = x); for (int i = 0; i < prime.size() && prime[i] <= lpf[x] && prime[i] * x <= n; ++i) lpf[prime[i] * x] = prime[i]; } } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << prime.size(); return 0; }  10.Improved Linear Eratosthenes Sieve#include #include using namespace std; const int LIM = 1e6; const int LIM_P = 664579 + 66; int cntPrime; int prime[LIM_P]; int lpf[LIM + 1]; void sieve(int n) { cntPrime = 0; prime[cntPrime++] = 2; fill_n(lpf, n + 1, 2); for (int x = 3; x <= n; x += 2) { if (lpf[x] == 2) prime[cntPrime++] = (lpf[x] = x); for (int i = 0; i < cntPrime && prime[i] <= lpf[x] && prime[i] * x <= n; ++i) lpf[prime[i] * x] = prime[i]; } } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  11.Atkin Sieve#include #include #include #include #include using namespace std; const int LIM = 1e6; int cntPrime = 0; bool isPrime[LIM + 1]; void sieve(int n) { memset(isPrime, false, sizeof(isPrime)); if (n < 2) return ; isPrime[2] = true; cntPrime = 1; if (n < 3) return ; isPrime[3] = true; cntPrime = 2; if (n < 4) return ; for (int x = 1; x * x <= n; ++x) { int A = x * x; for (int y = 1; y * y <= n - A; ++y) { int B = y * y, p; if (p = 4 * A + B, p <= n && (p % 12 == 1 || p % 12 == 5)) isPrime[p] = !isPrime[p]; if (p = 3 * A + B, p <= n && p % 12 == 7) isPrime[p] = !isPrime[p]; if (p = 3 * A - B, p <= n && p % 12 == 11 && x > y) isPrime[p] = !isPrime[p]; } } int rn = sqrt(n); for (int x = 5; x <= rn; ++x) if (isPrime[x]) for (int k = 1; k * x * x <= n; ++k) isPrime[k * x * x] = false; cntPrime = count(isPrime, isPrime + n + 1, 1); } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  12.Improved Atkin Sieve#include #include #include #include #include using namespace std; const int LIM = 1e6; int cntPrime; bool isPrime[LIM + 1]; void sieve(int n) { memset(isPrime, false, sizeof(isPrime)); if (n < 2) return ; isPrime[2] = true; cntPrime = 1; if (n < 3) return ; isPrime[3] = true; cntPrime = 2; if (n < 4) return ; for (int upx = sqrt(n / 4) + 1, x = 1; x <= upx; ++x) { int X = 4 * x * x; for (int upy = sqrt(n - X), y = 1; y <= upy; ++y) { int p = X + y * y; if (p % 12 == 1 || p % 12 == 5) isPrime[p] = !isPrime[p]; } } for (int upx = sqrt(n / 3) + 1, x = 1; x <= upx; x += 2) { int t = 1; int X = 3 * x * x; for (int upy = sqrt(n - X), y = 2; y <= upy; y += 6) { int p = X + y * y; isPrime[p] = !isPrime[p]; } for (int upy = sqrt(n - X), y = 4; y <= upy; y += 6) { int p = X + y * y; isPrime[p] = !isPrime[p]; } } for (int rn = sqrt(n), x = 1; x <= rn; ++x) { int X = 3 * x * x; for (int y = max(int(sqrt(X - n)) + 1, 1); y < x; ++y) { int p = X - y * y; if (p % 12 == 11) isPrime[p] = !isPrime[p]; } } int rn = sqrt(n); for (int i = 5; i <= rn; i += 2) if (isPrime[i]) for (int t = i * i, j = t; j < n; j += t) isPrime[j] = false; for (int i = 5; i <= n; i += 2) if (isPrime[i]) ++cntPrime; } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  13.Non-modulo Atkin Sieve#include #include #include #include #include using namespace std; constexpr int LIM = 1e6; int cntPrime; bool isPrime[LIM + 1]; void sieve(int n) { memset(isPrime, false, sizeof(isPrime)); if (n < 2) return ; isPrime[2] = true; cntPrime = 1; if (n < 3) return ; isPrime[3] = true; cntPrime = 2; if (n < 4) return ; for (int upx = sqrt(n / 4) + 1, x = 1; x <= upx; ++x) { int X = 4 * x * x; int t = 0; int b = (x % 3 == 0); for (int y = 1, p = X + y * y; p <= n; y += 2 + (b ? 2 * (t ^= 1) : 0), p = X + y * y) isPrime[p] = !isPrime[p]; } for (int upx = sqrt(n / 3) + 1, x = 1; x <= upx; x += 2) { int t = 1; int X = 3 * x * x; for (int y = 2, p = X + y * y; p <= n; y += 2 + 2 * (t ^= 1), p = X + y * y) isPrime[p] = !isPrime[p]; } for (int rn = sqrt(n), x = 1; x <= rn; ++x) { int X = 3 * x * x; int t = x & 1; for (int y = 1 + t, p = X - y * y; y < x; y += 2 + 2 * (t ^= 1)) { p = X - y * y; if (p <= n) isPrime[p] = !isPrime[p]; } } int rn = sqrt(n); for (int i = 5; i <= rn; i += 2) if (isPrime[i]) for (int t = i * i, j = t; j < n; j += t) isPrime[j] = false; for (int i = 5; i <= n; i += 2) if (isPrime[i]) ++cntPrime; } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  14.Improved Non-modulo Atkin Sieve#include #include #include #include #include using namespace std; constexpr int LIM = 1e6; constexpr int offset[2] = {2, 4}; constexpr int n3[3] = {1, 2, 0}; int cntPrime; bool isPrime[LIM + 1]; void sieve(int n) { memset(isPrime, false, sizeof(isPrime)); if (n < 2) return ; isPrime[2] = true; cntPrime = 1; if (n < 3) return ; isPrime[3] = true; cntPrime = 2; if (n < 4) return ; for (int upx = sqrt(n / 4) + 1, x = 1, x3 = 1, X = 4; x <= upx; ++x, x3 = n3[x3], X = 4 * x * x) { bool t = false; for (int y = 1, p = X + y * y; p <= n; y += (x3 ? 2 : offset[t ^= 1]), p = X + y * y) isPrime[p] = !isPrime[p]; } for (int upx = sqrt(n / 3) + 1, x = 1, X = 3; x <= upx; x += 2, X = 3 * x * x) { bool t = true; for (int y = 2, p = X + y * y; p <= n; y += offset[t ^= 1], p = X + y * y) isPrime[p] = !isPrime[p]; } // This code is slightly faster for (int rn = sqrt(n), x = 1, X = 3, v = 2, T = 1; x <= rn; ++x, X = 3 * x * x) { while (T * T <= X - n) ++T; bool t = x & 1; int y = 1 + t; if (X - y * y > n) y += (T - y) / 6 * 6; while (X - y * y > n) y += offset[t ^= 1]; for (int p = X - y * y; y < x; y += offset[t ^= 1], p = X - y * y) isPrime[p] = !isPrime[p]; } bool t = 1; int rn = sqrt(n); for (int x = 5; x <= rn; x += offset[t ^= 1]) if (isPrime[x]) for (int t = x * x, p = t; p <= n; p += t) isPrime[p] = false; for (int x = 5; x <= n; x += 6) cntPrime += isPrime[x] + isPrime[x + 2]; /// x is Prime or/and (x + 2) is Prime } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  15.Eratosthenes Wheel-2 Sieve#include #include using namespace std; const int LIM = 1e6; int cntPrime; bool isPrime[LIM / 2 + 1]; void sieve(int n) { memset(isPrime, true, sizeof(isPrime[0]) * (n / 2 + 1)); isPrime[0 / 2] = isPrime[1 / 2] = false; for (int p = 2; p * p <= n; ++p) if (isPrime[p / 2]) for (int x = p + p; x <= n; x += p) if (x % 2 == 1) isPrime[x / 2] = false; cntPrime = (n >= 2); for (int p = 3; p <= n; p += 2) if (isPrime[p / 2]) cntPrime += isPrime[p / 2]; } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  16.Improved Eratosthenes Wheel-2 Sieve#include #include using namespace std; const int LIM = 1e6; int cntPrime; bool isPrime[LIM / 2 + 1]; void sieve(int n) { memset(isPrime, true, sizeof(isPrime[0]) * (n / 2 + 1)); isPrime[0] = false; for (int p = 3; p * p <= n; p += 2) if (isPrime[p >> 1]) for (int x = p + p + p; x <= n; x += 2 * p) isPrime[x >> 1] = false; cntPrime = (n >= 2) + (n >= 3); for (int p = 5; p <= n; p += 6) cntPrime += isPrime[p >> 1] + isPrime[(p + 2) >> 1]; } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  17.Eratosthenes Wheel-2 Bitwise Sieve#include #include using namespace std; const int LIM = 1e6; int cntPrime; bitset isNotPrime; void sieve(int n) { isNotPrime[0] = true; for (int p = 3; p * p <= n; p += 2) if (!isNotPrime[p >> 1]) for (int x = p * p; x <= n; x += 2 * p) isNotPrime[x >> 1] = true; cntPrime = (n >= 2); for (int p = 3; p <= n; p += 2) cntPrime += !isNotPrime[p >> 1]; } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  18.Improved Eratosthenes Wheel-2 Bitwise Sieve#include #include using namespace std; typedef unsigned int uint; const uint LIM = 1e6; uint cntPrime; uint isNotPrime[(LIM >> 5) / 2 + 3]; uint get(uint p) { return (isNotPrime[p >> 5] >> (p & 31)) & 1; } void set(uint p) { isNotPrime[p >> 5] |= 1 << (p & 31); } void sieve(uint n) { isNotPrime[0] = true; for (uint p = 3; p * p <= n; p += 2) if (!get(p >> 1)) for (uint x = p * p; x <= n; x += 2 * p) set(x >> 1); cntPrime = (n >= 2) + (n >= 3); for (uint p = 5; p <= n; p += 6) cntPrime += !get(p >> 1) + !get((p + 2) >> 1); } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  19.Improved Erastothenes Wheel-2-3-5-7 Sieve#include #include #include #include #include using namespace std; #define all(x) (x).begin(), (x).end() const int LIM = 100000000; bool isPrime[(LIM + 1 - 7) / 2]; typedef unsigned int uint; constexpr uint WHEEL_1[] = {2, 1, 2, 1, 2, 3, 1, 3}; constexpr uint WHEEL_0[] = {1, 0, 1, 0, 1, 2, 0, 2}; constexpr uint NEXT8[] = {1, 2, 3, 4, 5, 6, 7, 0}; uint cntPrime; void sieve(uint n) { cntPrime = 0u; if (n < 2u) return ; cntPrime = 1u; if (n < 3u) return ; cntPrime = 2u; if (n < 5u) return ; cntPrime = 3u; if (n < 7u) return ; uint length = (n - 7u) / 2u; uint sqrt_lim = (sqrt(n) - 7u) / 2u; memset(isPrime, true, sizeof(isPrime[0]) * (length + 1)); for (uint i = 0u, w = 0u; i <= sqrt_lim; i += WHEEL_1[w], w = NEXT8[w]) if (isPrime[i]) { uint p = 7u + i + i; uint pa[] = {p, p + p, p + p + p}; for (uint j = (p * p - 7) / 2, m = w; j <= length; j += pa[WHEEL_0[m]], m = NEXT8[m]) isPrime[j] = false; } for (uint i = 0, w = 0; i <= length; i += WHEEL_1[w], w = NEXT8[w]) if (isPrime[i]) ++cntPrime; /// 7 + i + i is Prime } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  20.Improved Erastothenes Wheel-2-3-5-7 Segment Sieve#include #include #include #include #include using namespace std; typedef unsigned int uint; constexpr uint LIM = 1e6; constexpr uint NEXT8[] = {1, 2, 3, 4, 5, 6, 7, 0}; constexpr uint WHEEL_1[] = {2, 1, 2, 1, 2, 3, 1, 3}; constexpr uint WHEEL_0[] = {1, 0, 1, 0, 1, 2, 0, 2}; constexpr uint WHEEL_POS[] = {0, 2, 3, 5, 6, 8, 11, 12}; constexpr uint WHEEL_IDX[] = {0, 0, 1, 2, 2, 3, 4, 4, 5, 5, 5, 6, 7, 7, 7, 0, 0, 1, 2, 2, 3, 4, 4, 5, 5, 5, 6, 7}; constexpr uint WHEEL_DUP[] = {0, 2, 2, 3, 5, 5, 6, 8, 8, 11, 11, 11, 12, 15, 15, 15, 17, 17, 18, 20, 20, 21, 23, 23, 26, 26, 26, 27}; constexpr uint L1CACHEPOW = 14u + 3u; constexpr uint L1CACHESZ = (1u << (int)L1CACHEPOW); constexpr uint SEGSZ = L1CACHESZ / 15u * 15u; constexpr uint PRESZ = (65535u - 7u) / 2u; bool isPrime[PRESZ + 1]; bool segPrime[SEGSZ]; uint cntPrime; void sieve(uint n) { cntPrime = 0u; if (n < 2u) return; cntPrime = 1u; if (n < 3u) return; cntPrime = 2u; if (n < 5u) return; cntPrime = 3u; if (n < 7u) return; const uint upper = (n - 7u) / 2u; uint sqrt_upper = (sqrt(n) - 7u) / 2u; memset(isPrime, true, sizeof(isPrime)); for (uint i = 0u; i <= 124u; ++i) if (isPrime[i]) { uint p = 7u + i + i; for (uint j = (p * p - 7u) / 2u; j <= PRESZ; j += p) isPrime[j] = false; } for (uint i = 0u, w = 0u, si = 0u; i <= upper; i += WHEEL_1[w], si += WHEEL_1[w], si = (si >= SEGSZ) ? 0u : si, w = NEXT8[w]) { if (si == 0u) { memset(segPrime, true, sizeof(segPrime)); for (uint j = 0u, bw = 0u; j <= PRESZ; j += WHEEL_1[bw], bw = NEXT8[bw]) if (isPrime[j]) { uint p = 7u + j + j; uint k = p * (j + 3u) + j; if (k >= i + SEGSZ) break; uint pa[3] = {p, p + p, p + p + p}; uint sw = bw; if (k < i) { k = (i - k); k %= (15u * p); if (k != 0) { uint os = WHEEL_POS[bw]; sw = os + ((k + p - 1u) / p); sw = WHEEL_DUP[sw]; k = (sw - os) * p - k; sw = WHEEL_IDX[sw]; } } else k -= i; for (; k < SEGSZ; k += pa[WHEEL_0[sw]], sw = NEXT8[sw]) segPrime[k] = false; } } if (segPrime[si]) ++cntPrime; /// 7 + i + i is Prime } } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  21.Erastothenes Segment Sieve#include #include #include #include using namespace std; const int LIM = 1e6; const int SQRT_LIM = sqrt(LIM); bool isPrime[SQRT_LIM + 1]; int cntPrime; void sieve(int n) { int LIM = floor(sqrt(n)); vector prime; memset(isPrime, true, sizeof(isPrime[0]) * LIM); for (int p = 2; p * p <= LIM; ++p) if (isPrime[p] == true) for (int x = p + p; x <= LIM; x += p) isPrime[x] = false; cntPrime = 0; for (int p = 2; p <= LIM; ++p) if (isPrime[p]) { ++cntPrime; prime.push_back(p); } for (int low = LIM; low <= n; low += LIM) { int high = min(n, low + LIM); memset(isPrime, true, sizeof(isPrime[0]) * LIM); for (int i = 0; i < prime.size(); ++i) { int p = (low + prime[i] - 1) / prime[i] * prime[i]; for (int x = p; x <= high; x += prime[i]) isPrime[x - low] = false; } for (int n = low; n < high; ++n) if (isPrime[n - low] == true) ++cntPrime; } } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  22.Improved Erastothenes Segment Sieve#include #include #include #include #include using namespace std; #define all(x) (x).begin(), (x).end() const int LIM = 1e6; const int OPTIMAL_RANGE = 1 << 15; const int offset[2] = {2, 4}; int cntPrime; bool mark[OPTIMAL_RANGE]; bool isPrime[OPTIMAL_RANGE]; int seg_prime[OPTIMAL_RANGE]; int seg_multi[OPTIMAL_RANGE]; void sieve(int lim) { if (lim < 2) return ; int sqrt = std::sqrt(lim); int segment_size = max(sqrt, OPTIMAL_RANGE); memset(isPrime, true, sizeof(isPrime)); cntPrime = (lim >= 2) + (lim >= 3); int qdrt = std::sqrt(sqrt); for (int x = 5, t = 0; x <= qdrt; x += offset[t ^= 1]) if (isPrime[x]) for (int p = x * x; p <= sqrt; p += x) isPrime[p] = false; int n_seg = 0; int s = 5, n = 5; bool tn = 1, ts = 1; for (int low = 0; low <= lim; low += segment_size) { int high = min(low + segment_size - 1, lim); memset(mark, true, sizeof(mark[0]) * (high - low + 1)); for (; s * s <= high; s += offset[ts ^= 1]) if (isPrime[s]) { seg_prime[n_seg] = s; seg_multi[n_seg] = s * s - low; ++n_seg; } for (int x = 0; x < n_seg; ++x) { int p = seg_multi[x]; for (int k = seg_prime[x] * 2; p < segment_size; p += k) mark[p] = false; seg_multi[x] = p - segment_size; } for (; n <= high; n += offset[tn ^= 1]) if (mark[n - low]) ++cntPrime; } } int main() { int n; cin >> n; sieve(n); cout << "Number of primes up to " << n << " is " << cntPrime; return 0; }  23.Erastothenes Segment Bitwise SieveLost the original files.Lost the original files.
 » 7 months ago, # |   -8 It is already mentioned in YouKnowWho's The Ultimate Topic List. Present in Number Theory Section. Here is the direct link to the code