# Number of primes below a given number
**URL:** https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709
**Category:** Numerics
**Tags:** question
**Created:** [April 6, 2021, 6:36pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709 "2021-04-06T18:36:30Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@HexSpin](https://discourse.julialang.org/u/HexSpin)
#### Post date: [April 6, 2021, 6:36pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/1 "2021-04-06T18:36:30Z")
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
---
### Author:  [@aramirezreyes](https://discourse.julialang.org/u/aramirezreyes)
#### Post date: [April 6, 2021, 6:41pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/2 "2021-04-06T18:41:13Z")
You can do:
```julia
using Primes
primes(0,100) |> length
```
or equivalently
```julia
using Primes
length(primes(0,100))
```
---
### Author:  [@oheil](https://discourse.julialang.org/u/oheil)
#### Post date: [April 6, 2021, 6:41pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/3 "2021-04-06T18:41:57Z")
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.
---
### Author:  [@HexSpin](https://discourse.julialang.org/u/HexSpin)
#### Post date: [April 6, 2021, 7:04pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/4 "2021-04-06T19:04:24Z")
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](http://primesieve.org)) with this feature, so maybe it’s time for me to get comfortable with pulling in other functions…
---
### Author:  [@HexSpin](https://discourse.julialang.org/u/HexSpin)
#### Post date: [April 6, 2021, 7:05pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/5 "2021-04-06T19:05:17Z")
Sadly, I need the precise number.
---
### Author:  [@tlienart](https://discourse.julialang.org/u/tlienart)
#### Post date: [April 6, 2021, 7:56pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/6 "2021-04-06T19:56:21Z")
alternatively you could just look up tables: [Tables of values of pi(x) and of pi2(x)](http://sweet.ua.pt/tos/primes.html) there’s specifically a link for the first 10\_000 values of \pi(k\cdot 10^{14})
---
### Author:  [@oheil](https://discourse.julialang.org/u/oheil)
#### Post date: [April 6, 2021, 7:58pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/7 "2021-04-06T19:58:52Z")
> [@tlienart](#):
>
> alternatively you could just look up tables: [Tables of values of pi(x) and of pi2(x)](http://sweet.ua.pt/tos/primes.html) there’s specifically a link for the first 10\_000 values of π(k⋅1014)
This. (and there is no alternative)
---
### Author:  [@HexSpin](https://discourse.julialang.org/u/HexSpin)
#### Post date: [April 6, 2021, 8:17pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/8 "2021-04-06T20:17:21Z")
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!)
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [April 6, 2021, 8:24pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/9 "2021-04-06T20:24:07Z")
What is wrong with the `Primes.jl` solution? I think it’s using a SOE internally, so it should be pretty fast.
---
### Author:  [@HexSpin](https://discourse.julialang.org/u/HexSpin)
#### Post date: [April 6, 2021, 8:39pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/10 "2021-04-06T20:39:48Z")
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.
---
### Author:  [@j\_verzani](https://discourse.julialang.org/u/j_verzani)
#### Post date: [April 6, 2021, 9:11pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/11 "2021-04-06T21:11:21Z")
The answer here: [Prime Iterator in Julia - Stack Overflow](https://stackoverflow.com/questions/37142821/prime-iterator-in-julia) shows how to make an iterator using this definition of `nextprime` (edited to adjust to changes in Julia):
```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
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
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [April 6, 2021, 9:37pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/12 "2021-04-06T21:37:06Z")
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.
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [April 6, 2021, 9:39pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/13 "2021-04-06T21:39:32Z")
This will be incredibly slow. Prime sieves are way more efficient.
---
### Author:  [@HexSpin](https://discourse.julialang.org/u/HexSpin)
#### Post date: [April 6, 2021, 9:54pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/14 "2021-04-06T21:54:40Z")
Yes, I agree. Primesieve takes 0.01 sec to tell me there are 5761455 below 10^8. Thank you for thinking about it though. 🙂
---
### Author:  [@stillyslalom](https://discourse.julialang.org/u/stillyslalom)
#### Post date: [April 6, 2021, 10:45pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/15 "2021-04-06T22:45:32Z")
Using Primes.jl,
```julia
function countprimes(N)
Δ = round(Int, N^0.8)
sum(1:Δ:N) do n₀
count(primesmask(n₀, min(n₀ + Δ - 1, N)))
end
end
```
```julia
julia> @time countprimes(10^8)
0.241134 seconds (358 allocations: 37.440 MiB)
5761455
```
…so quite a bit slower than primesieve, but not awful.
---
### Author:  [@HexSpin](https://discourse.julialang.org/u/HexSpin)
#### Post date: [April 6, 2021, 11:09pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/16 "2021-04-06T23:09:38Z")
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… : /
---
### Author:  [@stillyslalom](https://discourse.julialang.org/u/stillyslalom)
#### Post date: [April 6, 2021, 11:18pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/17 "2021-04-06T23:18:02Z")
Yes, I suspect primesieve is using an analytical [prime-counting function](https://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_%CF%80(x)), which will be much faster than sieving.
---
### Author:  [@HexSpin](https://discourse.julialang.org/u/HexSpin)
#### Post date: [April 7, 2021, 1:11am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/18 "2021-04-07T01:11:28Z")
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.”
---
### Author:  [@stillyslalom](https://discourse.julialang.org/u/stillyslalom)
#### Post date: [April 7, 2021, 1:32am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/19 "2021-04-07T01:32:57Z")
Ah, I thought primesieve might use the author’s other library, [primecount](https://github.com/kimwalisch/primecount), but it appears not.
---
### Author:  [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)
#### Post date: [April 7, 2021, 2:38am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/20 "2021-04-07T02:38:38Z")
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.
[Next page](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709.md?page=2)