Number of primes below a given number

Specific Domains Numerics
1

I wish to find the number of primes below a given number, e.g. there are 25 primes below 100. It appears primes.jl does not do this and I can’t seem to locate a package to do so (at least not one compatible with OSX). I must be missing something… Thoughts?
Thanks,
Tad

1 Like
2

You can do:

using Primes
primes(0,100) |> length

or equivalently

using Primes
length(primes(0,100))
8 Likes
3

As far as I know, there isn’t a shortcut for the exact number, so you have to calculate them all. The approximation, on the otherhand, is trivial to calculate.

4

Thank you for your response. That would be a clever trick in most circumstances; however, I need values in ranges up to 10^14, which would quickly overwhelm my machine. I have a good sieve in Numpy (primesieve.org) with this feature, so maybe it’s time for me to get comfortable with pulling in other functions…

5

Sadly, I need the precise number.

6

alternatively you could just look up tables: Tables of values of pi(x) and of pi2(x) there’s specifically a link for the first 10_000 values of \pi(k\cdot 10^{14})

2 Likes
7

This. (and there is no alternative)

1 Like
8

Thanks! Not exactly what I was looking for, but I think it might do the trick if I’m unable to figure out some code. (And a generally interesting resource!)

9

What is wrong with the Primes.jl solution? I think it’s using a SOE internally, so it should be pretty fast.

10

Thanks Oscar – I’m unable to locate a command to make Primes.jl count primes.
I can quickly fill arrays with the primes themselves, I can find a prime above and below a value. It even offers some interesting co-prime functions… but I can’t seem to locate the prime counting button.

11

The answer here: Prime Iterator in Julia - Stack Overflow shows how to make an iterator using this definition of nextprime (edited to adjust to changes in Julia):

function _nextprime(y::BigInt)
           x = BigInt()
           ccall((:__gmpz_nextprime,:libgmp), Nothing, (Ptr{BigInt},Ptr{BigInt}), Ref(x), Ref(y))
           x
       end

(Something similar is wrapped in SymEngine.) Rather than wrap in the iterator interface,you should be able to just run something like this:

julia> function cntprimes(n)
       x=BigInt(1)
       cnt = 0
       while x <= n
       x = nextprime(x)
       cnt += 1
       end
       cnt-1
       end
cntprimes (generic function with 1 method)

julia> cntprimes(100)
25

It took awhile with 10^8 (21 seconds), so I have no idea how long this will take with 10^14

12

I meant using the function to get all the primes and counting the length of that. If you ask for primes in chunks, this takes O(1) extra memory and basically no extra time.

1 Like
13

This will be incredibly slow. Prime sieves are way more efficient.

1 Like
14

Yes, I agree. Primesieve takes 0.01 sec to tell me there are 5761455 below 10^8. Thank you for thinking about it though. :slight_smile:

15

Using Primes.jl,

function countprimes(N)
    Δ = round(Int, N^0.8)
    sum(1:Δ:N) do n₀
        count(primesmask(n₀, min(n₀ + Δ - 1, N)))
    end
end

julia> @time countprimes(10^8)
  0.241134 seconds (358 allocations: 37.440 MiB)
5761455

…so quite a bit slower than primesieve, but not awful.

3 Likes
16

Thank you for your thoughtful response! I’ll fiddle with it in AM… I suspected, once your raise this to 5 or 6 orders of magnitude, this quarter second will be 6 hours or more… : /

17

Yes, I suspect primesieve is using an analytical prime-counting function, which will be much faster than sieving.

18

He goes into detail about how it works on the site, but leads with “primesieve generates primes using the segmented sieve of Eratosthenes with wheel factorization. This algorithm has a run time complexity of operations and uses memory. Furthermore primesieve uses the bucket sieve algorithm which improves the cache efficiency when generating primes > 2^32. primesieve uses 8 bytes per sieving prime, hence its memory usage is about bytes per thread.”

19

Ah, I thought primesieve might use the author’s other library, primecount, but it appears not.

2 Likes
20

Making a BinaryBuilder package for the primecount program & library seems like it would be pretty easy and it seems to be the state of the art in fast prime counting. Someone could also probably port its algorithm to Julia without too much difficulty, although the code base is larger and more involved than one would naively expect.

7 Likes