### omggg's blog

By omggg, history, 3 years ago,

In many questions i feel if i am able to get primes upto 10^9, i can solve the problem but how do i do that?

I know Sieve upto 10^6. I know Segmented Sieve for U-L. But still i cant get primes upto 10^9. Please give me some idea. Any help will be much appreciated. Thanks a lot"

• +26

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +47 I know Sieve upto 10^6 I know sieve up to $10^8$. You can use std::bitset::_Find_next(bit) to find next prime.
•  » » 3 years ago, # ^ |   0 Thanks How does it work? Can you give me a little tutorial please on its working? THat would be great and much appreciatd.
•  » » 3 years ago, # ^ |   0 Had some fun codegolfing it and making it skip even numbers. https://ideone.com/zZGO5qThe skipping makes it be able to do 1e9 in 4.4 s on CF. The fastest sieve I know of (a segmented sieve) takes around 1.6 s on CF for 1e9, so 4.4s for so little code is pretty good.
 » 3 years ago, # |   +5 BTW, in which questions do you think it would be possible to solve by obtaining primes upto 10**9 efficiently? I am curious as I have solved some number theory problems and never encountered a problem which required this to be solved....
•  » » 3 years ago, # ^ |   0
•  » » » 3 years ago, # ^ |   0 You don't need to obtain primes up to 10**9 to solve that problem.
•  » » » » 3 years ago, # ^ |   0 Please give me the solution.
•  » » » » » 3 years ago, # ^ |   0 It's similar to this problem: 655F — Four DivisorsCheck the comments and editorial for that. You should be able to find the trick once you solve that problem.
•  » » 3 years ago, # ^ |   0 Obviously they were solved by some other observations where we didn't need it, but i felt that bruteforce kindof thing would work if i had primes upto 10^9
 » 3 years ago, # | ← Rev. 2 →   +41 Block sieving up to $10^9$ works 2.7s on CF. https://ideone.com/pNiP1M
 » 3 years ago, # | ← Rev. 4 →   -12 Segment Bitwise Eratosthenes Sieve is the fastest sieve I know to get primes number.The complexity is O(n log log n) time — O(sqrt(n)) spaceGetting primes in range [1, 1.000.000.000] under 0.3s in custom test (GNU G++ 17 7.3.0)Getting the 1.000.000 prime under 0.5s in custom test (GNU G++ 17 7.3.0) Code/// @author Kim Walisch, <[email protected]> /// @license Public domain. /// Use and edit spyofgame #include #include #include using namespace std; typedef unsigned char byte; int count = 0; vector primes; void sieve(int lim) { if (lim < 2) return ; int sqrt = std::sqrt(lim); int sieve_size = max(sqrt, (1 << 15)); int segment_size = sieve_size * 16; vector mark(sieve_size); vector is_prime(sqrt + 1, true); vector seg_prime; vector seg_multi; for (int i = 3; i <= sqrt; i += 2) if (is_prime[i]) for (int j = i * i; j <= sqrt; j += i) is_prime[j] = false; int reset[16]; for (int i = 0; i < 8; ++i) reset[2 * i] = reset[2 * i + 1] = ~(1 << i); int popcnt[256]; for (int i = 0; i < 256; ++i) popcnt[i] = __builtin_popcount(i); int s = 3; for (int low = 0; low <= lim; low += segment_size) { fill(mark.begin(), mark.end(), 0xff); int high = min(low + segment_size - 1, lim); sieve_size = (high - low) / 16 + 1; for (; s * s <= high; s += 2) { if (is_prime[s]) { seg_prime.push_back(s); seg_multi.push_back(s * s - low); } } for (size_t i = 0; i < seg_prime.size(); ++i) { int j = seg_multi[i]; for (int k = seg_prime[i] * 2; j < segment_size; j += k) mark[j >> 4] &= reset[j % 16]; seg_multi[i] = j - segment_size; } if (high == lim) { int bits = 0xff << ((lim % 16) + 1) / 2; mark[sieve_size - 1] &= ~bits; } for (int n = 0; n < sieve_size; n++) { // count += popcnt[mark[n]]; continue; for (int i = 0; i < 8; i++) if (mark[n] & (1 << i)) primes.push_back(low + n * 16 + i * 2 + 1); } } } int main() { int n; cin >> n; sieve(n); int p = primes.size(); cout << p << endl; return 0; } 
•  » » 3 years ago, # ^ |   +15 under 0.3ms Did you mean 0.3s? 0.3ms would mean you're producing ~50 primes per cpu cycle; that's probably very impossible. But also your code runs in 2.2s on CF (and 1.8s on my machine), so 0.3s doesn't seem right either.
•  » » » 3 years ago, # ^ | ← Rev. 4 →   -16 ah sorry, my mistake. Thanks for reminding me
 » 3 years ago, # |   0 I'm curious if anybody has feedback on the following experimental solution for this: Find them before runtime (using whatever seive you want), and then throw these numbers into a predefined array of integers that is created before runtime. There are 5x10^7 primes under 1 billion, which should with some prayer will fit into a 200 MB array I believe, thus avoiding MLE.I'm pretty sure your standard IDE wouldn't be too cheerful about you having that array defined in text, and I'm not sure codeforces would accept a 200 MB sized submission, but it's food for thought anyways, under the general theme of computations that are expensive, but whose results are not too big (here they probably are)
•  » » 3 years ago, # ^ | ← Rev. 4 →   +27 Actually you can store differences between consecutive elements and with some hacks I'm sure you can fit into 6 bits per element, so with some encoding like base64 it will be 50MB of sources. But it's still a lot and not worth it.Another interesting trick is to compute sieve in compilation time. And it really works, but because of some compiler limitations for constexpr calculations I was able to compute it only for $N = 5\cdot 10^5$, and for some really big $N$ it's hardly possible. Code#include using namespace std; constexpr int LOG2(int n) { return n <= 1 ? 0 : 1 + LOG2(n / 2); } template constexpr int ReturnSize = int(N * 1.6 / LOG2(N) + 100); template constexpr auto sieve() -> std::array> { std::array> primes = {}; int ps = 0; bool bs[N + 1] = {}; // compiler has limitation on the constexpr loops length, // so nested loops are used constexpr int B = 4096; for (int si = 2; si <= N; si += B) { int ei = si + B <= N ? si + B : N + 1; for (int i = si; i < ei; ++i) { if (!bs[i]) { primes[ps++] = i; if (i * 1LL * i <= N) { const int itCount = (N - i * i) / i + 1; int j = i * i; for (int sj = 0; sj < itCount; sj += B) { int cur = std::min(B, itCount - sj); for (int k = 0; k < cur; ++k) { bs[j] = 1; j += i; } } } } } } return primes; } constexpr auto primes = sieve<500000>(); int main() { int cnt = 0; for (int p : primes) { if (p == 0) break; ++cnt; } cout << cnt << endl; return 0; } 
•  » » » 3 years ago, # ^ |   0 Ah I see, cleverly taking advantage of compile time. Interestingly, some contests (to my knowledge, Codejam) regard compile time as part of the entire running time.
 » 21 month(s) ago, # | ← Rev. 4 →   -16 .
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 But this would not generate all primes upto $10^9$ or some limit. Also, the proof for infinite primes is something different entirely, it assumes that there are a finite number of primes, ${P_1, P_2, ..., P_k}$ and then goes on to show a contradiction. Since there aren't actually a finite number of primes, it's not guaranteed that a number generated like you say is not divisible by some of the later primes. In particular, $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031$ is not prime.In fact, the article you linked does say exactly the opposite of what you said!
 » 21 month(s) ago, # |   0 maybe you can try min_25 sieveO((n^0.75)/logn), very fast
•  » » 21 month(s) ago, # ^ |   0 And it uses lots of knowledge of function. Be careful!
 » 13 months ago, # | ← Rev. 2 →   -18 know yourslef