omggg's blog

How to get prime numbers upto 10^9 ?
By omggg, history, 5 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

Comments Comments (21)
| Write comment?
»
5 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.

→ Reply
  • »
    »
    5 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.

    → Reply
  • »
    »
    5 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.

    → Reply
»
5 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....

→ Reply
»
5 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

→ Reply
»
5 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
→ Reply
  • »
    »
    5 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.

    → Reply
»
5 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)

→ Reply
  • »
    »
    5 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
    → Reply
    • »
      »
      »
      5 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.

      → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it -16 Vote: I do not like it

.

→ Reply
  • »
    »
    3 years 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!

    → Reply
»
3 years 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

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

know yourslef

→ Reply