omggg's blog

By omggg, history, 2 years ago, In English

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"

 
 
 
 
  • Vote: I like it
  • +26
  • Vote: I do not like it

»
2 years ago, # |
Rev. 2   Vote: I like it +47 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
2 years ago, # |
Rev. 2   Vote: I like it +41 Vote: I do not like it

Block sieving up to $$$10^9$$$ works 2.7s on CF. https://ideone.com/pNiP1M

»
2 years ago, # |
Rev. 4   Vote: I like it -12 Vote: I do not like it

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

Code
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 4   Vote: I like it -16 Vote: I do not like it

      ah sorry, my mistake. Thanks for reminding me

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

  • »
    »
    2 years ago, # ^ |
    Rev. 4   Vote: I like it +27 Vote: I do not like it

    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
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
9 months ago, # |
Rev. 4   Vote: I like it -16 Vote: I do not like it

.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

maybe you can try min_25 sieve

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

A course in chinese

»
6 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

sieve