# 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:** 2

<div class="post-metadata">

**Author:** ![miguelraz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miguelraz/32/631_2.png) [@miguelraz](https://discourse.julialang.org/u/miguelraz)\
**Post date:** [April 7, 2021, 4:32am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/21 "2021-04-07T04:32:51Z")

</div>

[Pew pew](https://github.com/JuliaPackaging/Yggdrasil/pull/2778) @StefanKarpinski 😃

![](https://global.discourse-cdn.com/julialang/original/3X/8/0/80b0ed79d0f3b9472b4a6056205c1e5563be5036.gif)

---

<div class="post-metadata">

**Author:** ![miguelraz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miguelraz/32/631_2.png) [@miguelraz](https://discourse.julialang.org/u/miguelraz)\
**Post date:** [April 7, 2021, 4:49am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/22 "2021-04-07T04:49:12Z")

</div>

Also, if you ever think this BinaryBuilder.jl business is just Dark Arts By Those Compiler Gurus That I Just Will Never Learn About, I recorded myself doing a brief tutorial on how YOU could have done this.

[![](https://global.discourse-cdn.com/julialang/original/3X/a/4/a4416529de6ad9e1dcfb3009027fcb77a0549a20.jpeg "Your first BinaryBuilder.jl recipe with Julia") ](https://www.youtube.com/watch?v=7fkNcdbt4dg)

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [April 7, 2021, 5:39am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/23 "2021-04-07T05:39:27Z")

</div>

Bravo! 👏 It’s still mind blowing to me that that’s all it takes to build binaries that work on every platform where Julia runs and make it available to every Julia user.

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [April 7, 2021, 7:31am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/24 "2021-04-07T07:31:54Z")

</div>

Ready for use 🙂

```julia
julia> @time countprimes(10^8)
  0.172059 seconds (358 allocations: 37.440 MiB, 1.32% gc time)
5761455

julia> using primecount_jll

julia> @time run(`$(primecount()) 1e8`);
5761455
  0.007801 seconds (586 allocations: 67.656 KiB)

```

@HexSpin 10^14 you said? There you go:

```julia
julia> @time run(`$(primecount()) 1e14`);
3204941750802
  0.397191 seconds (586 allocations: 67.656 KiB)

```

---

<div class="post-metadata">

**Author:** ![yakir12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yakir12/32/297_2.png) [@yakir12](https://discourse.julialang.org/u/yakir12)\
**Post date:** [April 7, 2021, 8:02am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/25 "2021-04-07T08:02:26Z")

</div>

```julia
julia> @time solve_this_thing;
  13 hours

```

Julia ❤

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [April 7, 2021, 9:06am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/26 "2021-04-07T09:06:36Z")

</div>

Looking at the orgs of some the contributors of [GitHub - JuliaPackaging/Yggdrasil: Collection of builder repositories for BinaryBuilder.jl](https://github.com/JuliaPackaging/Yggdrasil) I get the impression that what it took to master Binary Building was the need to compile half century old fortran code. There is a theme here of course.

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [April 7, 2021, 11:51am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/27 "2021-04-07T11:51:27Z")

</div>

I suspect you are correct …

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [April 7, 2021, 11:55am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/28 "2021-04-07T11:55:40Z")

</div>

Amazing. This has to be the best solution. I’ll get back to you as soon as I overcome whatever it is causing this error code I keep getting. Thank you, Miguel Raz!  
(What a crazy cool community).

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [April 7, 2021, 12:43pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/29 "2021-04-07T12:43:00Z")

</div>

I wrote a package that, among other things, does this. It uses the previous binary deps system. The package has fallen into disrepair. IIRC, I made an interface that combined primecount and lookup tables. The package does a few things that might be better split up. At the time I wrote it, it was much faster than other Julia packages for prime pi, prime sieves, etc. And just to be clear: using a sieve to compute the prime pi function is inefficient.

> **[GitHub - jlapeyre/PrimeSieve.jl: fast generation and counting of primes](https://github.com/jlapeyre/PrimeSieve.jl)**
>
> fast generation and counting of primes. Contribute to jlapeyre/PrimeSieve.jl development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [April 7, 2021, 1:34pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/30 "2021-04-07T13:34:40Z")

</div>

Do you happen to know how your prime generation performs against Kim Walisch’s primesieve benchmarks? A faster than primes.jl tool with your listed functions would be wonderful…but, alas, I’m on OSX so all academic (If I’m reading your notes correctly).

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [April 7, 2021, 2:28pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/31 "2021-04-07T14:28:31Z")

</div>

PrimeSieve.jl wraps a few C/C++ libraries, including Kim Walisch’s libprimesieve.

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [April 7, 2021, 2:34pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/32 "2021-04-07T14:34:08Z")

</div>

> [@HexSpin](#):
>
> I’m on OSX so all academic (If I’m reading your notes correctly).

I most likely wrote that note seven years ago, so the availability of libraries might have changed. I suppose there is a way to build osx libraries and make them available as well.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [April 7, 2021, 3:44pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/33 "2021-04-07T15:44:48Z")

</div>

I’m not volunteering you to do this or anything, but just so you know, it’s usually very easy these days to do what @miguelraz did and make a BinaryBuilder recipe that compiles C/C++ libraries for all supported platforms. The way BB works is that it compiles all binaries using the same Linux-based tool chain, configured to cross-compile for each platform. (Making that work was the part that required wizardry, but pay no attention to the man behind the curtain!) So getting a thing to compile in that one simple Linux environment is often enough to generate binaries for all platforms, including macOS, Windows and FreeBSD.

The binaries that are produced still need to interact with their native systems correctly, so for libraries that interact with the platform extensively, configuring them to cross-compile correctly can still be tricky, but for purely numerical libraries like this, it’s usually trivial since they pretty much take numbers as input, do some compute and give you numbers back out without ever needing to do anything platform-dependent. Once the binaries are built by Yggdrasil, they can just be downloaded onto end-user systems and used as-is with no modifications, and of course Pkg does that for you automatically. The whole thing is pretty magical and makes distributing binary dependencies super reliable and reproducible.

---

<div class="post-metadata">

**Author:** ![giordano](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/giordano/32/2166_2.png) [@giordano](https://discourse.julialang.org/u/giordano)\
**Post date:** [April 7, 2021, 4:53pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/34 "2021-04-07T16:53:32Z")

</div>

`primecount_jll` v6.5.0 comes with the shared libraries `libprimecount` and `libprimesieve` in addition to the `primecount` executable. Wait for [https://github.com/JuliaRegistries/General/pull/33760](https://github.com/JuliaRegistries/General/pull/33760) to be merged

---

<div class="post-metadata">

**Author:** ![miguelraz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miguelraz/32/631_2.png) [@miguelraz](https://discourse.julialang.org/u/miguelraz)\
**Post date:** [April 7, 2021, 5:07pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/35 "2021-04-07T17:07:47Z")

</div>

Thanks to @giordano , we have AVX2 speedups from the most recent build 💪

```julia
julia> using primecount_jll

julia> @time run(`$(primecount()) 1e8`);
5761455
  0.011614 seconds (467 allocations: 33.562 KiB)

julia> @time run(`$(primecount()) 1e14`);
3204941750802
  0.181341 seconds (467 allocations: 33.562 KiB)

julia> versioninfo()
Julia Version 1.6.0
Commit f9720dc2eb (2021-03-24 12:55 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-4710HQ CPU @ 2.50GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, haswell)

(@v1.6) pkg> st primecount_jll
      Status `~/.julia/environments/v1.6/Project.toml`
  [ba3b429d] primecount_jll v6.5.0+0

```

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [April 7, 2021, 5:17pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/36 "2021-04-07T17:17:49Z")

</div>

Perhaps this could be incorporated as a `primecount()` function into `Primes.jl`?

---

<div class="post-metadata">

**Author:** ![miguelraz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miguelraz/32/631_2.png) [@miguelraz](https://discourse.julialang.org/u/miguelraz)\
**Post date:** [April 7, 2021, 5:23pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/37 "2021-04-07T17:23:38Z")

</div>

Yup - that would add a dependency to `primecount`, but I think that’s accessible. If any newcomers want to PR that, feel free to DM and I’ll mentor through the process.

Concretely, we wouldn’t want to spawn an external process with `run(...)` every time we want to count primes - we want to call to the C ABI with `@ccall` so that this is just a direct function call:

```julia
julia> myprimecount(x) = @ccall libprimecount.primecount_pi(x::Clonglong)::Clonglong
myprimecount (generic function with 1 method)

julia> @time myprimecount(1e8)
  0.001004 seconds
5761455

julia> @time myprimecount(1e14)
  0.149201 seconds
3204941750802

```

This would include wrapping up the different options in the [exposed command line options](https://github.com/kimwalisch/primecount#command-line-options) with appropriate dispatches.

This means that your mission, should you choose to accept it, would be a Pull Request to Primes.jl that

1. adds `primecount_jll` as a dependency (easy: fork the repo, dev the repo, activate the environment, and add `primecount` as a normal package).
2. add functions + dispatch for all the appropriate `@ccall`s exposed in the commandline options in `primecount`’s README.
3. add tests to make sure that everything you added works.

Once that’s done, a good open source citizen would also PR the `primecount` github repo’s README to add Primes.jl as an Julia wrapper in their documentation (and/ or buy `kimwalish` et al a coffee).

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [April 7, 2021, 5:58pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/38 "2021-04-07T17:58:05Z")

</div>

Also enough people from JuliaMath here to figure out if we want that right away.

---

<div class="post-metadata">

**Author:** ![miguelraz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miguelraz/32/631_2.png) [@miguelraz](https://discourse.julialang.org/u/miguelraz)\
**Post date:** [April 7, 2021, 9:04pm UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/39 "2021-04-07T21:04:42Z")

</div>

Bonus round:  
The same author has a library for calculating the sum of prime numbers up to `n`.

[https://github.com/kimwalisch/primesum](https://github.com/kimwalisch/primesum)

---

<div class="post-metadata">

**Author:** ![stabbles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stabbles/32/946_2.png) [@stabbles](https://discourse.julialang.org/u/stabbles)\
**Post date:** [April 8, 2021, 7:17am UTC](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709/40 "2021-04-08T07:17:48Z")

</div>

Note that [https://github.com/haampie/FastPrimeSieve.jl](https://github.com/haampie/FastPrimeSieve.jl) is more or less a native julia implementation of libprimesieve. More or less because it doesn’t do tricks for fast prime sieving of large prime numbers (2^32 to 2^64), for \< 2^32 I would expect similar performance.

There’s an open PR to merge this sieve into Primes.jl.

Libprimecount apparently uses a special algorithm with better time complexity to just count primes. So if you just want to count them and don’t want to do anything interesting with them, libprimecount will beat FastPrimeSieve.jl.

[Previous page](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709.md?page=1)

[Next page](https://discourse.julialang.org/t/number-of-primes-below-a-given-number/58709.md?page=3)