Recognizing three-digit primes
by John from John D. Cook on (#6BK7W)
If a three-digit number looks like it might be prime, there's about a 2 in 3 chance that it is.
To be more precise about what it means for a number to look like a prime," let's say that a number is obviously composite if it is divisible by 2, 3, 5, or 11. Then the following Python code quantifies the claim above.
from sympy import gcd, isprime obviously_composite = lambda n: gcd(n, 2*3*5*11) > 1 primes = 0 nonobvious = 0 for n in range(100, 1000): if not obviously_composite(n): nonobvious += 1 if isprime(n): primes += 1 print(primes, nonobvious)
This shows that out of 218 numbers that are not obviously composite, 143 are prime.
This is a fairly conservative estimate. It doesn't consider 707 an obvious composite, for example, even though it's pretty clear that 707 is divisible by 7. And if you recognize squares like 169, you can add a few more numbers to your list of obviously composite numbers.
The post Recognizing three-digit primes first appeared on John D. Cook.