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

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

enter image description here

| cite | improve this answer | |
  • $\begingroup$ Just wondering, whats the software you used to make that graph? $\endgroup$ – FireCubez Oct 10 '19 at 18:29
  • $\begingroup$ The graph (and the calculation) were done in Matlab. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ This is nice, but is there a faster one? (I commonly use this to determine primality) $\endgroup$ – 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
or this one on using elliptic curves

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

| cite | improve this answer | |
  • $\begingroup$ I think this test is only possible with a computer $\endgroup$ – zscoder May 6 '14 at 10:50
  • $\begingroup$ 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 $\endgroup$ – notacat May 6 '14 at 10:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.