I once heard it asserted that $91$ is the smallest composite number that is not obviously composite. The reasoning was that any composite number divisible by $2$, $3$, or $5$ is obviously composite, and the only composite numbers less than $91$ that are not divisible by $2$, $3$, or $5$ are $49$ and $77$, and it's obvious that those are obviously composite.
I'm going to go out on a limb and wildly guess that $577$ might be the largest prime number that is as obviously prime, or at least as quickly and easily seen to be prime as it is.
It's obviously not divisible by $2$, $3$, or $5$, and $7$ and $11$ are instantly rejected since subtraction of $77$ from this number leaves $500$, and $13$ is rejected since this number plus $13$ is $590$ so we've reduced it to thinking about the two-digit number $59$, and likewise subtracting $17$ from this number leaves $560$, and $56$ is not divisible by $17$, and subtracting $7$ leaves $570$ and $57$ is divisible by $19$, so we reject $19$. Finally, adding $23$ gives $600$, so we reject that, and there's no occasion to go higher than $23$ since $23+1 = 24=\lfloor\sqrt{577}\rfloor$.
So staring at it for ten seconds gives you the answer without writing anything or doing any divisions or looking at factorizations of nearby numbers that don't reduce instantly to two-digit problems. It's not unusual to reject a bunch of primes by doing this, but rejecting all of them by instantaneous reduction to one- or two-digit problems I don't recall seeing before.
Are there any bigger primes than $577$ where this is so quick and simple?
Best Answer