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

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. [Your first BinaryBuilder.jl recipe with Julia]

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… : /

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

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 i…

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

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 involv…

Pew pew @StefanKarpinski :smiley: [image]

Bravo! :clap: 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.

Ready for use :slight_smile: 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> @time solve_this_thing; 13 hours Julia :heart:

Looking at the orgs of some the contributors of GitHub - JuliaPackaging/Yggdrasil: Collection of builder repositories for BinaryBuilder.jl 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.

Number of primes below a given number

Specific Domains Numerics

miguelraz April 7, 2021, 4:32am 21

Pew pew @StefanKarpinski

Topic		Replies	Views
Using Binarybuilder binary New to Julia	3	503	May 27, 2021
Prime number hunting New to Julia	2	834	November 27, 2023
Fast Generation of Arrays of Prime Numbers Offtopic	32	1593	October 4, 2023
Finding and Printing prime numbers New to Julia	4	3645	April 1, 2019
Can Julia do this algorithm faster? Offtopic question , performance , algorithm	57	4888	June 27, 2022

Number of primes below a given number

Related topics