potter's blog

By potter, history, 7 months ago, In English

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.

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

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

    Can you share the same for python?

»
7 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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 code
»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

It is already mentioned in YouKnowWho's The Ultimate Topic List. Present in Number Theory Section. Here is the direct link to the code