Primal: Putting Raw Power Into Prime Numbers


#1

Over the past few weeks I’ve been working on improving my slow_primes library, culminating in needing rename and the 0.2 release of primal, a Rust crate for computing properties of prime numbers with state-of-the-art algorithms, while still maintaining an idiomatic and easy-to-use interface.


#2

Huon, thanks for a really useful crate! I’ve used primal quite a bit to solve the problems at projecteuler.net. Very fast and fun!

Have you considered adding a probabilistic primality checker? Something like Miller-Rabin. In my experience, MR is useful not only when checking huge primes, but also when doing a great number of calls to is_prime().

Thanks again for an awesome crate!
-Joe


#3

Wow, thanks for the kind words! I’m glad it’s useful.

There is the is_prime function, which uses Miller-Rabin in a deterministic way (instead of testing against some random witnesses, it uses specific witnesses which are known to correctly classify all numbers inside specific ranges, collectively covering everything from 0 to 264). Maybe you’re imagining something else?


#4

thanks, I will try primal::is_prime (I had been using is_prime() from a Sieve instance). Frankly I missed primal::is_prime(). My fault for not reading the docs more carefully.


#5

OK, done, switching from sieve.is_prime() to primal::is_prime() sped up my program by 15X (!). Thanks again.