Vanekss's blog

Count of primes ≤ 10^12
By Vanekss, history, 6 months ago, In Russian

Hello codeforces,I'm trying to solve a problem on acmp, in this problem I only need to count the number of primes up to 10^12,do you know some algorithms to solve it?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I have a funny solution to this problem: split the range $$$1 \ldots 10^{12}$$$ into blocks of length $$$B$$$. Locally precompute number of primes in each block (might take some time), then you can calculate $$$\pi(n)$$$ in about $$$O(B)$$$ time.

Set $$$B$$$ somewhere between $$$10^7 \ldots 10^8 $$$ to get AC. For higher $$$B$$$ you might not have enough time to process $$$O(B)$$$ numbers and for lower $$$B$$$ you might not fit into code size limit (which is $$$2^{17}$$$ bytes on acmp).

→ Reply