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"

I know sieve up to $$$10^8$$$. You can use

`std::bitset::_Find_next(bit)`

to find next prime.Thanks How does it work? Can you give me a little tutorial please on its working? THat would be great and much appreciatd.

Had some fun codegolfing it and making it skip even numbers. https://ideone.com/zZGO5q

The 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.

Can you tell how to print those primes till 1e9?

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....

Problem E: https://drive.google.com/file/d/16ohrSa1WvpOQZLXkI8gsOdQyZm8mBjJd/view https://algo.codemarshal.org/contests/mist-ncpc-2020/problems/E

You don't need to obtain primes up to 10**9 to solve that problem.

Please give me the solution.

It's similar to this problem: 655F — Four Divisors

Check the comments and editorial for that. You should be able to find the trick once you solve that problem.

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

Block sieving up to $$$10^9$$$ works

2.7son CF. https://ideone.com/pNiP1MSegment 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)) space

Getting 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)

CodeDid 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.

ah sorry, my mistake. Thanks for reminding me

min_25's sieve that I coped from his blog on ideone take's around 0.6s till 1B, but having seen his timing on spoj I am sure he has done more optimizations on top of that, so 0.3s is quite possible.

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)

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.

CodeAh 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.

You can find some tips on Fast Prime Sieve github. I've based my fast sieve on the prime_sieve.c (you can find this link on that github page). It uses segmented sieve with wheel optimisation in base { 2, 3, 5}. I've rewritten the code in the relatively compact form. Sorry, it's still hardly understandable. Another even more compact fast sieve you can find here.

I checked these https://ntheory.org/sieves/benchmarks.html but even the fastest library (till 10^9) ie Kim Walisch's was not as fast as min_25's sieve. I checked zimpha's segmented-wheel-sieve as well. It is quite fast as well but slightly slower than min_25. Many of the above libraies are cache efficient and thread efficient code. Which neither min_25's nor zimpha's single file code is this shows we have lot more headrooms to improve.

.

But this would not generate

allprimes upto $$$10^9$$$ or some limit. Also, the proof for infinite primes is something different entirely, it assumes that there are afinitenumber 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!

maybe you can try min_25 sieve

O((n^0.75)/logn), very fast

A course in chinese

And it uses lots of knowledge of function. Be careful!

sieve