How to identify a prime number without a computer
14 comments
·November 12, 2025IsTom
GMoromisato
Are there any numbers that don't look prime but are, in fact, prime? [Other than 2, I suppose.]
throwaway81523
Like the famous Grothendieck prime of course.
xorbax
Definitely makes me feel better about my own work
emaccumber
The annoying child in me will always remember correcting my freshman math teacher when he needed a prime number and wrote 91 on the chalkboard.
null
Nevermark
Just grab some paper, a pen, and check that no number equal or smaller than its square root divides into it evenly.
That is it. That is all. Pish posh.
WCSTombs
The example given in the article is 2^127 - 1, which was historically proved to be prime without computers using a clever method now known as the Lucas-Lehmer test. Your algorithm is not practical for that number.
Nevermark
Ah, but I can assure you, it is just that simple.
If a number is not prime, then it is the product of at least two numbers smaller than itself.
If any of them are larger than its square root, the all others must be smaller, or their product would be larger than the candidate prime.
Ergo, just check that the candidate is not evenly divisible by any number equal or lower than its square root.
QED. Check mate. Shazam.
great_wubwub
/r/whoosh
politelemon
This is behind a paywall. "A Subscription Is Required to Continue Reading"
zamadatix
The scourge of HN submission rules - "you can submit anything and it's up to everyone else to actually be able to access it".
Terr_
If I had my 'druthers designing a new link-share/comment system, the visibility (and mirrors or excerpts) for the target would be part of the model.
In other words, an icon showing whatever-wall status, submitter can add an alternate link, etc.
xeonmc
I guess that's the answer then -- you need a subscription instead of a computer.
My favourite prime checking algorithm is that for n < 100 if it looks prime, it is prime.