Hacker News new | past | comments | ask | show | jobs | submit login
Is This Prime? (isthisprime.com)
196 points by jordigh 65 days ago | hide | past | favorite | 132 comments

This reminds me of my favorite in-person magic trick to do.

First, memorize all the two-digit primes. 25 numbers isn't that hard to memorize.

Then, tell someone "Oh, I can instantly tell whether a number is prime or not. Give me a number, I'll tell you whether it's prime."

If they tell you a number between 1 and 100, use your memorized list. Otherwise, it's a game of cold reading; if they just generated a random string of many digits, there's a low chance that the number actually is prime. "21923847" is a keysmash, and it's almost certainly not prime, because the frequency of primes goes down as numbers get bigger. And most people will ask you a number, hear "no", and then go check the number's primality. Eventually, they'll look up a number in advance; that number is almost certainly prime.

And then one day, somebody asks you calmly: "what about 2^31-1"? Better memorise the small Mersenne exponents as well!


Also, most composites are divisible by 2, 3 or 5, all of which are very easy to check (for 3 just sum up the digits and if the result is divisible by 3, the original number is divisible by 3). 49, 77, and 91 are the only composites under 100 that is not divisible by one of those 3 numbers, making memorizing 25 numbers not even necessary. 49 and 77 are obviously composite to me making 91 the only number I bothered memorizing.


53 is prime

Oh, shoot, brain fart. I was thinking OP was listing primes and forgot one. :D


Only 14 away from a prime though


5+7=12 thus divisible by 3 and not prime

After 8 attempts, I ran into "Game Over". Was just thinking about the satisfaction for the author of this site. There is just enormous fun in saying - Game Over - to another human :)

Somehow I've memorised 10243 in order to have a "big prime" that most people can't just determine. Note its the lowest 5 digits.

I'm always using 1000003 and 1000000009 if I need a big prime in code. Million 3, billion 9 - very easy to remember

I've now memorized 10247, the second-lowest over 5 digits. Everyone else get in line.

I hope the twin prime conjecture holds, since it would be pretty incredible to think that, despite what you said, there are infinitely many twin primes.

That's a lot of effort just for tricking people into thinking you can tell if a number is prime.

I love these simple web games! Great idea. One way to improve it is to add some more juice when you answer a question. Right now, the text in the number just swaps to the next question, so any sort of small visual feedback will help first time players get it more.

I also like to make these small web mini games on the side. Here's one where you guess the year that famous events happened: https://guess-the-year.davjhan.com/

If I click start, then paste some quick and dirty browser automation in the console:

  function c(){is_prime(document.getElementById('n').textContent)==="prime"?yes.click():no.click();window.setTimeout(c,1)};c()
My old laptop can guess right 16k times and get up to 4172973243025599, but then the http post to do the stats (record.php) bombs with a MySql error "Out of range value for column 'end' at row 1" :)

I guess it wouldn’t be HN if your side project’s database didn’t crash because you didn’t choose the right data type, haha. Looks like it gracefully failed though, could be worse. I’m afraid that the stats page is too easy to DDOS though.

look at the entries lol, looks like it had an injection heyday back when first released

That made me wonder how the game determines if the number is a prime or not. Turns out it's the Miller-Rabin test with a deterministic variant used for the range (up to 2^53) the game supports. I don't know why the game internally uses a bigint implementation while only supporting numbers up to 2^53 though...

Here is a "theorem" I learned: every number up to 100 which looks prime, is prime, except 91. Does anyone recall its name?

This is a great "theorem", thank you!

It's easy to determine divisibility by 2, 3, 5, and 11. 7² is also easy because it's a square. 7×13=91 is the only composite number under 100 that isn't caught by these rules.

A trick for remembering that 91 is composite is that it's of the form x² - y² (specifically 10² - 3²), so it's (x+y)(x-y) or 13 * 7.

seems easier to remember "91 is composite"

Really like that! Presumably this is because most people's sense of what feels prime is: odd numbers which don't appear in the times tables; and only 39, 51, 57, 69, 87, 91 and 93 are red herrings in that regard, all of which bar 91 are divisible by 3, which people also have a good sense of, not least by using the add the digits rule.

Don’t know the name of the “theorem”, but I know the rhyme:

  91 is not a prime
  that one trips me every time.

But that doesn’t really help you remember 91, because the number is not part of the rhyme.

49 looks prime to me. Another commentator says it doesn't count because it's a square number, but square numbers don't really have a particular "look" to me in the same way that 2-digit numbers ending in 5 or with digits summing to a multiple of 3 do.

Your maths teacher didn't force you to memorize squares then.

I did memorize the sequence and still have it memorized, but I have to enumerate them. They don't have a "look" to them.

There's no "look" for me either. But I immediately know that 49 is not prime because I recognize it as the answer to one of the times table math problems that I learned.

Based on my failure at this game, anything times 19 looks prime to me.

Well you only have 4 of those under 100.

The "looks prime" rule assumes you check for multiples of 3, so that removes one.

All the rest end in an even digit or 5.

yeah once i started doing the trick for 3's the whole thing got boringly easy

I think it's called "The Ridiculous Fish Theorem."

+1... I lost two games in a row, both times on 91.

Dammit, that's the one that got me on my first try.

I agree. And I would add 51 to that.

51's an easy one because 5+1=6, and 6 is divisible by 3, so it must be divisible by 3.

It's easy to try 'divisible by 5' (ends in 5 or 0) and 'divisible by 3' (sum of digits is divisible by 3). 91 isn't found as prime by those two tests, so it needs the extra exceptional rule.

Of course! I actually know of this divisible by 3 rule, and use it to test out all numbers, like 87, 111, or 69, but somehow forget to apply it to 51…

They have stats on the most common mistakes here: https://isthisprime.com/game/record.php (loads very slowly)

51 is #1, then 57, then 1

It’s very surprising to me that 91 isn’t in the top 20. It’s beaten by 77 and 21?

i got got by 67 on my first try. something about it just gave me non-prime vibes.

When I was a fifth grader in China, we were required to memorize all prime numbers below 100.

Curious if that is common in other countries?

It isn't standard in the US, although at some point I memorized them to prepare for buzzer races in math competitions. It was in no way reflective of anything useful in real life, but it was fun.

There were a few sets of common numbers, formulas, and mental calculation tricks that were useful to just always have in the back of your head. Perfect squares and cubes under 1000, powers of 2 and 3, prime numbers below 100, interior angles of regular polygons up to 10 sides, binomial coefficients, Pythagorean triples, factorials up to 9!, common roots out to 3-4 decimal places, and a few others that I've no longer needed for almost 20 years at this point.

How is that useful?

It is very useful in the context of Chinese grade school. There are a lot of exam problems that require factorization, and calculators are banned. Having a list of primes memorized comes really handy.

Frivolous memory tasks as a measurement of bureaucratic aptitude?

Lol right because I never had to memorize the multiplication tables, states capitols, electron shell levels and numbers, periodic tables, etc in the US

Vast majority of my school experience wasn't useful

When I was a fifth grader we were required to memorize all prime numbers below 20.

We memorized pi to 7 decimal places... a few memorized it to 20+

    Now I, even I, would celebrate
    In rhymes unapt, the great 
    Immortal Syracusan, rivalled (sic) nevermore
    Who, in his wondrous lore,
    Passed on before,
    Left men his guidance
    How to circles mensurate.

Indeed. But I find "How I want a drink, alcoholic of course, after the heavy lectures involving quantum mechanics." sufficient for most of my needs.

I don't think that was a thing in France (at least where I went to school) but we often used them indirectly to simplify fractions, so all in all maybe we had to know all primes under 25 I think?

I don't think so. Remember any other interesting numbers list you needed to memorize?

I learned all the integers.

What is the highest integer you know?

If I were able to count them out loud, in order? 999 nonillion, 999 octillion, 999 septillion, 999 sextillion, 999 quintillion, 999 quadrillion, 999 trillion, 999 million, 999 thousand, 999.

That is (after consulting a table), 1 decillion - 1.

I clearly come from from a short scale culture. If I switched to the long scale and Chuquet names I could, of course, go to 999 nonilliard, 999 nonnillion, 999 octilliard, etc.


n + 1 ∀ n ∈ N

that's not an integer, that's a set

Finally a way to sort out candidates that's even cheaper than making them implement B-trees.

After lots of 2-digit numbers ending in 5 came up, my brain went on autopilot thinking "any number that ends in 5 is not a prime". I lost when 5 came up.

I'm not sure why but having 'yes' be on the left is really messing me up.

You must be a macOS or iOS user.

Or Android.

So a solid majority of all computer users.

I've started, if I wake up in the middle of the night, thinking of a 'prime-looking' number, then trying to factor it. Sometimes I discover interesting connections, other times I fall back asleep - either is a win.

Good practice for learning divisibility rules https://en.m.wikipedia.org/wiki/Divisibility_rule

This is really cool! I made a very similar game a couple years ago: https://jew.ski/prime-time/

It's interesting to compare the game play and design. My game is written in Elm and open source if anyone is interested. This website has keyboard inputs (y or n) which is a good idea. My game only does click/touch inputs.

man, these tech screenings are getting out of control

Is there a reason we're obsessed with primes beyond aesthetics? Why does this set of numbers garner all the headlines as opposed to some other arbitrary integer sequence like the Recamán numbers [0] ?

If tomorrow someone discovered a closed-form equation for the nth prime, how would mathematics/the world change?

[0] https://en.wikipedia.org/wiki/Recamán%27s_sequence

The prime numbers are critical in cryptography. Almost all of our current digital security infrastructure is based on the concept of multiplying large numbers together modulo suitably big prime numbers.

Any major step towards understanding them (such as a closed-form equation for primes) would have major mathematical knock-on effects which may or may not undermine these methods, or provide us with a basis for even stronger cryptographic mechanisms to make use of in the future.

>Almost all of our current digital security infrastructure is based on the concept of multiplying large numbers together modulo suitably big prime numbers.

That's not true of elliptic curves.

Elliptic curve cryptography uses modulo of large prime numbers. Curve25519 uses 2^255 - 19 for example

I'm not sure about a closed-form equation for the nth prime, but if integer factorization can be done in linear time then much of applied cryptography needs to be replaced.

None is known. Can't be a polynomial.

There are two main operations for whole numbers: addition and multiplication. A basic question is what are the "atoms". With respect to addition, the atom is 1, since every number can be written as a sum of 1's, and 1 isn't itself a nontrivial sum. With respect to multiplication, the atoms are the primes, where primes aren't nontrivial products.

A cool thing about breaking a number into multiplicative atoms (the "prime decomposition") is that to multiply two numbers, you can just add up however many copies there are of each atom. Primes turn multiplication into addition in this way. In other words, each prime defines a sort of logarithm that measures the amount of that prime in a number, and knowing the "coordinate" in prime space is enough to determine the original number.

Then one might wonder what is the relationship between primes and addition. When you add two numbers, the prime decomposition of the result seems to be dramatically different from the decompositions of the summands. But there are patterns, like how the sum of even numbers is even. The abc conjecture[1] has to do with one of these patterns.

The relative order of the primes also is saying something about the relationship between addition and multiplication, since addition underlies how you compare two numbers. There are old results about the density of the primes as if they were following a random distribution.

I'm not sure if there's any deep structure that Recamán's sequence has anything to do with. All that seems to be interesting about it is that it evades our capabilities of determining whether every number eventually appears. The Collatz conjecture is similar in this way, though it is further complicated by the fact that it mixes the structures of multiplication and addition.

[1] https://en.wikipedia.org/wiki/Abc_conjecture

Going deeper, in algebraic geometry, what you do is take various number systems (called "rings" -- the integers are an example of a ring) and pretend each element is a function that measures some scalar quantity about an associated space. It's a bold and wild idea. There is a process by which you can figure out what the points of this associated space are, and, at least for the integers, there is one point for each prime. If you think about an integer n as a function defined on this space, then the evaluation of n at the point p ends up being equal to n mod p. All I'm trying to say by bringing this up is that primes are not just aesthetic, they have deep significance, with many analogs in other kinds of mathematics.

Beyond cryptography, there is the fundamental theorem of arithmetic, which plays an important role in encoding Gödel numbers in Gödel's theorem.

In algebra, the integers mod p are a finite field (addition, subtraction, multiplication, and division are defined) if and only if p is prime.

Primality in algebra also exists in a more general form with prime ideals. An ideal is the set of elements of a commutative ring in which any element of the ideal multiplied by any element of the ring is still in the ideal; there is a sort of 'closed' property. Even numbers form an ideal because if you multiply any number by an even number, you get an even number. For a prime ideal, if ab is in the ideal, a is in the ideal or b is (similar to how if a prime number divides ab, it divides a or b).

They have a number of interesting properties. For example, for a ring homomorphism (a function from one ring to another that preserves relationships between elements of the two rings), the pre-image of a prime ideal is also a prime ideal.

prime numbers let you abstract away parts of math that would normally require bruteforce to solve in the human mind.

Remember finding the common denominator in school, or reducing fractions to their lowest form. both require guess work to do the normally taught way, but both can be achieved using prime factorization in a "set" way that resolves to a solution.

I struggled in grade school to do fractions purely because of reducing and common denominators, but ended up tutoring people how to do them in college pre-algebra because thats when I learned about prime factors and what you can do with them.

If i had learned algebra before basic fractions i likely wouldn't had needed to dropout of high school and get a ged.

> If tomorrow someone discovered a closed-form equation for the nth prime, how would mathematics/the world change?

Btw, that kind of exists. There's a formula that produces nothing but prime numbers. It basically encodes sieving, and it coincidentally uses every letter of the English alphabet.


Your original link 404'd on me (you seem to have replaced it with a different one though). Here's the working Wikipedia link:


Thanks. I've edited the link.

Love it. But if you are clicking an answer just as time is running out, you won't get to see your score (it starts a new game).

I've spent a good week of straight hours on primes by now, the most fun thing I've come up with was this boring sieve.


Coding Ulam's Spiral is also fun:


I was expecting an Amazon product search / review site and was pleasantly surprised that it is in fact a math game.

I'm using this as a metric to determine if my brain is deteriorating. (my age) + (my best score, without more than a few minutes of 'training') > 80 means I'm still doing OK.

Today, at 56 years wise, I scored 34, so 90 > 80. Means I judge myself to be smart enough to put my shoes on the correct feet, still.

I am not doing _that_ type of number crunching in my daily work, so the following check (in Python) has probably lots of potential for improvement:

    def is_prime(n):
        return not True in [n%x == 0 for x in range(2, n/2)]

You don't need to test up to n/2, just floor(sqrt(n)) will do

even better you only need to test the primes <= floor(sqrt(n))

I think this question is framed the wrong way for me. I think if the question was "Is this composite?" I would get much better scores. The way I think is "Does it have a factor?" and inverting that Boolean trips me up.

My prime number skills only go up to 47 because that's how high Number Munchers went.

I was too busy shooting more meat than I could carry back to the wagon, or fleeing low to escape the osprey.

I love it, but the game doesn't work for me! No response when I click Yes or No, or using the keyboard y and n. Just the clock ticking down. Chrome Version 91.0.4472.114 (Official Build) (64-bit) on Windows 10 Enterprise.

I’ve always wondered: how feasible is it to implement an “isprime” function, via lookup table? If such methods are used, is cryptography getting weaker and weaker in practice as more large primes are discovered?

No, at the cryptographic scale of prime numbers the lookup table would need to be far too big in terms of both time to generate and storage required.

For smaller numbers see various prime sieves (Atkin, Eratosthenes)

Time to generate I get, but you could always augment the table over time and fall back to standard methods otherwise (and store the result).

Storage I have a harder time wrapping my head around. Aren’t primes quite sparse at cryptographic magnitudes? And are the primes used for (say) 256-bit encryption about the same magnitude, narrowing the dimension of storage required?

The primes are quite dense. There are roughly n/log(n) primes below n. Meaning 1 in 256 numbers with 256 bits are prime. That's 2^(248) primes.

For RSA one typically use 2048 or 4096 bit primes.

Natural logarithm (base e, not base 2, so one in 177.4 for 256 bit numbers), but that doesn't change your general point.

If your question is purely "is the value prime" the Fermat primaility test is very fast, probably about as fast as a hash table lookup on a table that large. Running Baillie–PSW to eliminate false positives isn't a huge deal either as it will only need to run if Fermat passes. It's not a horrible idea on its face and may indeed be a little faster, at the cost of lots of memory. I don't know of a use case where it would be worth it.

I really like it.

I wonder if the text could be dropped once it starts. I found myself reading it each time which ended up distracting me a little and sometimes I would rush and tapped the opposite of what I intended.

Why do I feel like I'm solving someone else's CAPTCHA?

PSA: you can use the arrow keys to answer more quickly.

78. Who did better?

I was hoping someone would post a score. I got 35, but I kept getting distracted.

Wow, you're hired!

Great game!

Keyboard short cuts would make it a bit better.

The help text says y and n work, I’m on mobile and haven’t tried though.

Y and N for yes and no.

you can use left and right arrows

> 1 is non-prime by definition.

This made me sad :(

In practice, it turns out to be more convenient if the definition excludes 1, rather than put a qualifier in every place which uses the term "prime".

For example, it's more convenient to write "every integer greater than 1 is a unique product of prime numbers" than to say "every integer greater than 1 is a unique product of {prime numbers excluding 1}"

(That's the fundamental theorem of arithmetic https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme... .)

Game over

1 is non-prime by definition.

You correctly sorted 17 numbers.

Cool! Now let's try to find a way to make this fit in a fast paced space shooter.

What about a Pac-Man?

https://www.youtube.com/watch?v=xKrn5bHn-d8 - Mathman, from the PBS series "Square One Television". A Pac-Man spoof. In this one Mathman must only eat primes.

Would pay to for more chances


They've included 1 as not a prime. That was a fairly recent decision.

One is not a prime number. If you allow one to be a prime number, then you can no longer say that each natural number has a unique prime factorization.

This makes the concept of prime numbers much more useful when one is excluded.

> If you allow one to be a prime number, then you can no longer say that each natural number has a unique prime factorization.

I don't dispute that, by definition, 1 is not prime, but I don't see how this statement would follow if we considered it prime.

Edit: it seems more like it would be that every factorization would implicitly have 1^n tacked onto it, and while that isn't exactly useful, it doesn't break the game.

That breaks the uniqueness of the prime factorization. Mathematicians love uniqueness, almost as much as existence.

Could you please demonstrate an example of such a break? I think if we really look at it, we might see that it's really just convention and semantics. I don't want to seem like I'm cherry picking by providing my own example.

The unique prime factorization of 15 is 3⋅5.

Let's call a number an Igelau prime if it is the number 1 or a prime number. Then an Igelau prime factorization of 15 is 3⋅5. Another Igelau prime factorization of 15 is 1⋅3⋅5. Another Igelau prime factorization of 15 is 1²⋅3⋅5. And so on. There are infinitely many Igelau prime factorizations of 15, thus there is no uniqueness.

Edit: Clarifying what Igelau primes are.

Basically it's excluded because many theorems become cumbersome to state.

Endlessly saying "primes other than 1" gets kind of tedious.

and there will be no prime numbers above 1 if 1 is considered a prime (based on existing definitions) Though if you think about it they can just modify the definition in that case

The definition I usually use (speaking loosely for the moment) is that prime numbers are natural numbers greater than one whose divisors are only one and itself.

Speaking more formally, a natural number p is a prime if and only if:

a) p > 1

b) for any natural number n satisfying 1 < n < p, p mod n ≠ 0

It's not a recent decision. It's a (low grade) debate that's spanned thousands of years now.

Who's they? Is this a mathematical consensus?

"they" is the game developers of this game.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact