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

I need a quick way to determine whether a number is prime by hand. Any suggestions?

• Have you tried google? – Dmoreno May 6 '14 at 10:42
• Why is it important for you to do this by hand? – KCd May 6 '14 at 10:47
• Well, when I'm participating in a math contest XD – zscoder May 6 '14 at 10:48
• @zscoder If you participate to a math contest, you should know immediately that $4\,294\,967\,297$ is not prime. – egreg May 6 '14 at 11:10
• All primes except for $2$ and $3$ are of the form $6n\pm1$. – Lucian May 6 '14 at 11:26

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? • Just wondering, whats the software you used to make that graph? – FireCubez Oct 10 '19 at 18:29
• The graph (and the calculation) were done in Matlab. – Chris Taylor Oct 10 '19 at 19:07

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.

• This is nice, but is there a faster one? (I commonly use this to determine primality) – zscoder May 6 '14 at 10:48

edit: if you are doing it by hand read this one www-math.mit.edu/phase2/UJM/vol1/DORSEY-F.PDF

You can try running some probabilistic primality tests such as: https://en.wikipedia.org/wiki/Fermat_primality_test