Test primes up to the square root

Divide by 2, 3, 5, 7 and on, and stop only when the next prime squared is bigger than the number

Where to stop testing

Testing 91÷ 2no÷ 3no÷ 5no÷ 7= 13
9 × 9 = 81, so the primes up to 9 are enough.

A prime number is a whole number greater than 1 with exactly two positive divisors: 1 and itself. To show a number is not prime, find one divisor. To show it is prime, you must know there is none.

More

Test prime divisors in order: 2, 3, 5, 7, 11, 13 and so on. Stop when the next prime squared is bigger than the number. Any larger factor would need a smaller partner, and you have tested all the small ones.

1Find the largest whole number whose square is not above the number.

2Divide by each prime up to it.

3One exact division means not prime. None means prime.

Lesson help

Test every prime whose square is not above the number, and stop only after the last one.

About this lesson

Try the method in a practice when you are ready.

Report

Where to stop testing

A prime number is a whole number greater than 1 with exactly two positive divisors: 1 and itself. To show a number is not prime, find one divisor. To show it is prime, you must know there is none.

Test prime divisors in order: 2, 3, 5, 7, 11, 13 and so on. Stop when the next prime squared is bigger than the number. Any larger factor would need a smaller partner, and you have tested all the small ones.

1Find the largest whole number whose square is not above the number.

2Divide by each prime up to it.

3One exact division means not prime. None means prime.

Testing 91÷ 2no÷ 3no÷ 5no÷ 7= 13
9 × 9 = 81, so the primes up to 9 are enough.

Is 91 prime?

9 × 9 = 81 and 10 × 10 = 100, so test the primes up to 9: 2, 3, 5, 7.

91 is odd, its digits add to 10, and it does not end in 0 or 5. But 91 ÷ 7 = 13 exactly, so 91 = 7 × 13 and it is not prime.

97 goes through the same four tests with no exact division, so 97 is prime.

Testing 97÷ 2no÷ 3no÷ 5no÷ 7no
None of 2, 3, 5, 7 divides 97.

Is 221 prime?

None of 2, 3, 5, 7 and 11 divides 221. Decide whether that is enough.

Testing 221÷ 2no÷ 3no÷ 5no÷ 7no÷ 11no
Five primes tested so far. None divides 221.

Try it

Is 221 prime?

  1. Prime
  2. Not prime
Show the answer

Not prime

Right. 14 × 14 = 196 is below 221 and 15 × 15 = 225 is above, so test up to 14. 13 divides it: 221 = 13 × 17.

Enable JavaScript to answer interactively and save your place.

Practice Prime or not?

Sign in free

Practice without limits and keep your progress.