maths.free › Number Theory › Prime numbers

Prime numbers

Testing for primality by trial division up to the square root.

A prime has no divisors except 1 and itself. To test n, try the primes up to √n only — if n had a factor larger than √n, it would also have one smaller. For enormous numbers this is too slow and probabilistic tests take over, but the idea is the same.

Worked example: is 97 prime

Number-Theory · Prime-Numbers

Is 97 prime

97

Step by step

  1. \sqrt{97} \approx 9

    Only primes up to √97 need testing: any factor above it pairs with one below.

  2. 97 \bmod 2 = 1

    2 does not divide 97.

  3. 97 \bmod 3 = 1

    3 does not divide 97.

  4. 97 \bmod 5 = 2

    5 does not divide 97.

  5. 97 \bmod 7 = 6

    7 does not divide 97.

  6. \text{97 is prime}

    No prime up to the square root divides it, so it has no factors other than 1 and itself.

Reveal the answer
\text{97 is prime}

Try your own

More in Number Theory

Prime factorisationGCD and LCMModular arithmeticDivisorsSequencesNumber bases