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

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


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.


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

Tags:

Prime Numbers

Related

Integral $\int_0^1 \log \Gamma(x)\cos (2\pi n x)\, dx=\frac{1}{4n}$ Pie Integral $\int_0^1 \log\frac{(x+\sqrt{1-x^2})^2}{(x-\sqrt{1-x^2})^2} \frac{x\, dx}{1-x^2}=\frac{\pi^2}{2}.$ Career advice: Mathematical neuroscience Duality 2-functor on adjunctions What are well-defined functions? The proof of $e^x \leq x + e^{x^2}$ Prove or disprove inequality $\frac{a^2}{b+c}+\frac{b^2}{a+c}+\frac{c^2}{a+b}\le\frac{a^4+b^4+c^4}{2abc}$. Let $|G|=p^nm$ where $p$ is a prime and $\gcd(p,m)=1$.Suppose that $H$ is a normal subgroup of $G$ of order $p^n$. For $x_{n+1}=x_n^2-2$, show $\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$ If $h : Y \to X$ is a covering map and $Y$ is connected, then the cardinality of the fiber $h^{-1}(x)$ is independent of $x \in X$. Equivalent ideas of absolute continuity of measures A non-abelian group such that $G/Z(G)$ is abelian.

Recent Posts