Funfunfunfun's blog

Counting prime numbers smaller than n.
By Funfunfunfun, history, 4 years ago, In English

The other day I met a problem that needed to count the number of primes less than n with n <= 1e10. But I only know how to use sieve to solve but it can only run with n <= 1e6. Can you help me find a better solution? thanks for help!

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

Comments Comments (10)
| Write comment?
»
4 years ago, # |
  Vote: I like it -24 Vote: I do not like it

use segmented sieve, you can easily find videos of it on youtube

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Thank your idea.This is the good sieve but this can run with n<=1e8.I think another better way to solve this problem.

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

      there exists approximate prime counting function, which gives very accurate result for small N

      → Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I had the same curiosity a while ago, so I wrote some code to find pi(n) (which is what you need) and prime(n) (n-th prime number). You can play with N and X constants to see which gives better times. Here is the code. I used Meissel–Lehmer algorithm. You can read here and here about it. If you don't understand, don't be shy and ask me! Happy new year! :D

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I don’t understand how to calculate Pi(x,a). Can you explain it to me?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      In my code it's the function P(niv, n, a) which, I think, it's pretty clear how it works

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        I understood. Thanks you so much!

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          But can you explain me X in your code for what?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it -8 Vote: I do not like it

            Yes sure. X is max i so that we calculate Pi(n, a). Increasing X, lowers initial a, but it might cause P function to take much more time. After testing, I found that X should be 6 or 7.

            → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://en.wikipedia.org/wiki/Meissel%E2%80%93Lehmer_algorithm

→ Reply