# 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

or read this for some more info on primality tests
www-math.mit.edu/phase2/UJM/vol1/DORSEY-F.PDF
or this one on using elliptic curves
groups.csail.mit.edu/cis/pubs/shafi/1999-jacm.pdf

without any more information it's hard to know exactly what you are looking for

• I think this test is only possible with a computer – zscoder May 6 '14 at 10:50
• www-math.mit.edu/phase2/UJM/vol1/DORSEY-F.PDF there are some you can do by hand here, such as the one based on fermat's little theorem – notacat May 6 '14 at 10:55