A quick way to determine whether a number is prime by hand? [closed]

Solution 1:

There's no super-fast way to determine if an arbitrary number is prime by hand. However, you can often quickly determine when a number isn't prime, which is often good enough, especially if you are only dealing with smallish numbers, as you often are in math competitions.

• If a number ends in 0, 2, 4, 5, 6 or 8 then it's not prime (except for 2 and 5)
• If the sum of the digits is a multiple of 3, then the number is not prime (except for 3)

Those two rules knock about nearly 75% of numbers.

For numbers below 100, the only false positives are $49=7^2$, $77=7\cdot 11$ and $91=7\cdot 13$ which you can learn.

Divisibility by 7

A number of the form $10x+y$ is divisible by 7 exactly when $x-2y$ is divisible by 7. This allows you to quickly reduce the size of a number until you reach a number that obviously is or isn't a multiple of 7. For example, consider $n=847 = 84\times 10 + 7$. Then $x-2y$ is $84 - 14 = 70$ which is obviously divisible by 7, so 847 is also divisible by 7.

Divisibility by 11

There is also a simple test for multiples of 11 - starting from the units place, add the first digit, subtract the next digit, add the next one and so on. If you end up with a negative number, treat it as positive. If the result is a multiple of 11, so is the original number.

For example, take $n=539$. You calculate $9-3+5=11$, which is a multiple of 11, and so 539 is a multiple of 11.

Using these rules to check for divisibility by 2, 3, 5, 7 and 11 the only false positive less than 200 is 169, which is easy to remember as it is $13^2$. The only false positives below 300 are $221=13\times 17$, $247=13\times 19$, $289=17^2$ and $299=13\times 23$.

Edit: Just for fun, here's a graph of how many false positives there are for a given upper bound. This chart shows that with four rules and a list of 13 exceptions, you can correctly find whether any number under 500 is prime or not in... probably 20-30 seconds?

Solution 2:

To determine if $n$ is prime:

1. Find the biggest perfect square $k^2 \le n$.

2. Write out all the primes less than or equal to $k$.

3. Test if $n$ is divisible by each of said primes on your list.

   • If $n$ is divisible by any of the primes, $n$ is not prime.

   • If $n$ is divisible by none of the primes, $n$ is prime.