Primality test up to $\sqrt n$

#primality test#sqrt#trial division

Statement

Test whether $97$ is prime.

Hint

Test divisibility by primes up to $\sqrt{97}\approx9.8$ .

Show solutionHide solution

Primes to test. $2,3,5,7$ .

Divisibility.
- $2$ : odd.
- $3$ : digit sum $16$ , not divisible by $3$ .
- $5$ : ends in $7$ .
- $7$ : $97=7\cdot13+6$ , remainder $6$ .

Conclusion. $97$ is prime.