15
$\begingroup$

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

$\endgroup$
  • 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
19
$\begingroup$

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 | |
$\endgroup$
  • $\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
7
$\begingroup$

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 | |
$\endgroup$
  • $\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
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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.