Issue 22

Let’s build a prime detector!

Bror Hjemgaard gets out his numerical toolbox

post

17 November 2025

Primes—they were my introduction to the mysticism of mathematics, and I’ve had a soft spot for them ever since. My only problem with them is how elusive they are—whenever I discover a cool new number, I’ve always got to go out of my way to check whether it is prime or not… Wouldn’t it be better if there were some function which just told us if a number is a prime?

Well, of course it would! And to construct such a function, we could always take the easy route by simply defining a function $p$ such that
\begin{align*} p(x) \equiv \begin{cases} \;1 &\text{ if $x$ is prime,} \\ \;0 &\text{ if $x$ is not prime.} \end{cases} \end{align*}

This $p(x)$ unequivocally succeeds in being a prime detector, but it is rather… boring. While nothing is stopping us from taking this $p(x)$ and running off into the sunset with it, I am assuming that you, as a reader of Chalkdust, would be a tad more interested in a more captivating (and fun) mathematical story about prime detectors.

Our aim today is therefore to build a prime detector from the ground up using some pretty simple mathematics. Specifically, the detector we will be constructing is one which I built myself back in high school. Yes, built.

I very much view this form of mathematics as a cross between logical programming and analytic number theory: we will start with basic logical operations and combine them in such a way to observe the emergence of a non-trivial mathematical function. As such, we aim for a function which not only detects primes, but also illustrates the overlap shared between programming and mathematics—a function which you could easily program and play around with yourself. Our goal is therefore not to derive the most efficient, ingenious or resourceful prime number detector, but rather to have fun and hopefully rekindle that magic we so fondly remember from playing around with mathematics in our youth. And who knows; maybe you will learn a thing or two along the way.

The construction

Before we start building our prime detector, we are going to take a detour through the land of functions. For our journey, we will be rather lenient with the term ‘function’: as long as it takes in a number and spits out a number, I am OK with it. We place no restrictions on things like analyticity or continuity because our goal is to have fun, and let’s face it—maths is at its most fun when we invite as many functions as possible to the party.

The hero of our adventure is going to be a favourite function of mine, the floor function: \[\lfloor x \rfloor\] The floor function ‘floors’ the number $x$ by removing any decimal components! For example, $\lfloor 0.823 \rfloor = 0$, $\lfloor \mathrm{e} \rfloor = 2$, $\lfloor -1.5 \rfloor = -2$. With the floor function we can do all sorts of cool tricks. For example, we can extract the decimal part of any number: $\pi – \lfloor \pi \rfloor = 0.1415926535 8979323846 2643383279 502884197 \dots$

The decimals of an arbitrary $x$ are therefore $x-\lfloor x \rfloor$. If $x$ is a whole number it does not have any decimals, meaning we have inadvertently built a whole number detector:

The awkward part about this detector is of course the ‘some number’ part. This ‘some number’ has to be greater than 0 and less than 1. (Can you see why?)

It would be much neater if the detector were binary in its output: 1 if whole number, 0 if not. Let’s fix that.

To solve the ‘1-if-whole-number’-part, I propose to use that $a^0 = 1$ for any non-zero number $a$. Hence, simply raising $a$ to the power of our original detector, we get an updated version:

At first glance, this looks as awkward as version 1.0, but I claim that this is a step in the right direction! If $a$ happens to be a number between 0 and 1, this ‘some other number’ will also be between 0 and 1 (can you see why?).

For example, for $a=0.3$ and $x=\pi$, version 1.1 spits out 0.843265…, and for $a=0.1$ and $x= \mathrm{e}$, it outputs $0.191301\dots$ We can then apply the floor function to this output to get 0 when $x$ is not a whole number—just like we wanted. When $x$ is a whole number, we still have $\lfloor a^0\rfloor = 1$. Any $a$ between 0 and 1 will suffice, so we will go with $a=1/2$. This gives us an updated (and now binary!) whole number detector:

This is neat, but it could be neater. Notice that since $\frac{1}{2}= 2^{-1}$ we can factor the power of –1 into the exponent and write the entire expression as:

How elegant! How simple! How beautiful! “How will this help us detect primes?” you ask? Well, primes have a very intimate relationship with whole numbers.

If we wish to check if an integer $n$ is prime or not, we need to first check if 2 is a divisor of $n$, then if 3 is a divisor, and so on. Another way of writing ‘is $m$ a divisor of $n$?’ is ‘is $n/m$ a whole number?’ and we’ve got a detector for that! So if we input $x=n/m$ into the whole number detector for $m=$2, 3, …, $n-1$, we can manually check if $n$ is divisible by any number smaller than itself, which of course constitutes a prime check.

Come to think of it, do we really need to check if $n$ is divisible by every $m$ up to $n-1$? I mean, for larger numbers like $n=109$ it is unreasonable that a sizeable number like $n-1=108$ could be a factor… In fact, it turns out that if $n$ isn’t prime, it must have a prime divisor less than or equal to $\sqrt{n}$ (can you see why?), so we need only check up to $\sqrt{n}$ (or rather, since $\sqrt n$ is potentially not a whole number, we check up to $\lfloor \sqrt n \rfloor$).

Since our whole number detector is binary, we can add together the results from all these tests. If this sum equals 0, it means that the whole number detector failed for all $m=2, 3, \dots, \lfloor \sqrt n \rfloor$, so $n$ must be prime. If $n$ is not prime, the sum will equal the number of divisors less than $\sqrt{n}$ of $n$. Our very first prime detector therefore looks like:

Great! We built a prime detector! Now, some people might leave it here and call it a day, but we mathematicians still have work to do. Wouldn’t it be neater if this prime detector were binary, ie 1 if prime, 0 if not prime?

To address this, we have to find a function $f(x)$ which takes whole numbers $x$ and has the properties $f(0) = 1$ and $f(x>0) = 0$. If we can find such a function then we need only insert our prime detector for $x$ in $f(x)$ to get a binary prime detector. There are tons of valid options for $f(x)$, and here are some of mine: (Can you find more?)

\begin{align*} f(x) &= \left \lfloor \frac{1}{1+x}\right \rfloor, \\ f(x) &= \left\lfloor \mathrm{e}^{-x} -\mathrm{e}^{-1}\right\rfloor +1, \\ f(x) &= \frac12\Big(1-\left \lfloor \arctan(\pi x)\right \rfloor\Big) \quad \text{(in radians),} \end{align*} All these examples feature our dear floor function. I have not been able to find an $f(x)$ which does not use the floor function, so do let me know if you find one!

Let us pick the first of these functions, to get our new (now binary!) prime detector:

OK, I will level with you—this is a rather ugly expression. I will forever cringe at a large sum in a denominator, so we will quickly tidy up the mess we have made. Notice that if we evaluate the summand (the term inside the summation expression) for $m=1$, we get 1. This is because any number $n$ is divisible by 1, and the summand simply checks if $n/m$ is a whole number. We can therefore pretend like the 1 which precedes the sum in the denominator originates from an $m=1$ term in the sum, and instead sum from $m=1$ to $m=\lfloor \sqrt n \rfloor$. Note that we only do this for aesthetic reasons. If you’d like to keep the sum from $m=2$, that is fine too.

Combined, this gives our final expression:

There we go—a prime detector! If you want, there are several ways to make it your own. For example, the 2 can be replaced by any number larger than 1 (remember: we arbitrarily picked $a=1/2$). You could also use any of the other $f(x)$ or even construct your own whole-number-detector! For those that would like a go at the latter, I’ll give a hint: $|\cos( x)| = 1$ when $x$ is an integer multiple of $\pi$ (NB! Radians).

That’s it for today. Happy priming!

Bonus: Mills’ constant

When talking about the floor function and primes, I just have to mention Mills’ constant, which is a real number denoted $A$ that has the property that $\lfloor A^{3^n}\rfloor$ is a prime number for any positive integer $n$. Excuse me‽ What on earth does the floor function have to do with such a remarkable claim? And why is there a 3 in there?

Let’s try to stay calm. Firstly, what is the value of $A$? Quite frankly, we do not know. We do know that it does exist, but we don’t know its value. However, if the Riemann hypothesis happens to be true, we can determine its value! In this case, Mills’ constant comes out to be approximately 1.306377883863… (sequence A051021 in the OEIS). Somehow this poor number is related to (perhaps) the biggest conundrum in all of mathematics, and right in the middle of this soup sits the floor function. If you ask me, Mills’ constant is the perfect mathematical snack—it connects highly studied and seemingly unrelated areas of mathematics, like the floor function, primes and the Riemann hypothesis, yet it is shrouded in mystery.

So let’s entertain ourselves and assume the Riemann hypothesis is true. Although $A$ is a rather small number, it will be raised to the power of $3^n$, which simply put grows exponentially. It comes as no surprise that the Mills primes very quickly become very large:

While researchers have calculated up to the 13th(!) Mills prime, anything this large is too unwieldy to ever be able to fit within a single issue of Chalkdust. I was actually unable to find any full publication of the Mills primes for $n>6$. If you do find any (or manage to calculate them yourself), please do send me them!

This truly illustrates the power of the floor function! Not only can it help us detect primes, but through Mills’ constant it can also help us generate them. Of course, neither approach is practical: Mills’ primes grow astronomically fast, and our formula is a brute force toy. Still, it’s neat to see the contrast: the humble floor function both (conditionally) conjures primes and (inefficiently) checks them.

Bror is a PhD student of theoretical physics at Imperial College London, where he usually works with quantum field theory and causal sets, but his first love will always be mathematics. His favourite number is 313 and he plays the harmonica.
All articles by Bror

More from Chalkdust