Factors and Multiples

Prime Check

Decide whether 17 is prime by testing prime divisors up to the square root of 17. If none divide 17 evenly, the number is prime.

Example

Test whether 17 has any prime factor up to its square root.

highlighted = computed this step

Step 1 — Set up

Set up the numbers to test.

prime check: 17\mathrm{prime\ check:}\ 17
Test prime divisors up to sqrt(17).sqrt(17) is between 4 and 5test primes: 2, 3test 2not tested yettest 3not tested yetprime verdict waits for both tests

Step 2 — Test 2

Test divisibility: 17 ÷ 2 = 8 remainder 1.

17÷2=8 r 117 \div \hl{2} = 8 \ \mathrm{r}\ \hl{1}
Try 2: 17 ÷ 2 = 8 remainder 1.sqrt(17) is between 4 and 5test primes: 2, 3test 217 ÷ 2 = 8 r 1remainder not 0test 3not tested yetprime verdict waits for both tests

Step 3 — Test 3

Test divisibility: 17 ÷ 3 = 5 remainder 2.

17÷3=5 r 217 \div \hl{3} = 5 \ \mathrm{r}\ \hl{2}
Try 3: 17 ÷ 3 = 5 remainder 2.sqrt(17) is between 4 and 5test primes: 2, 3test 217 ÷ 2 = 8 r 1remainder not 0test 317 ÷ 3 = 5 r 2remainder not 0prime verdict waits for both tests

Step 4 — Verdict

17 is prime because no prime up to sqrt(17) divides it.

17 is prime because no prime up to sqrt(17) divides it\text{17 is prime because no prime up to sqrt(17) divides it}
No tested remainder is 0, so 17 is prime.sqrt(17) is between 4 and 5test primes: 2, 3test 217 ÷ 2 = 8 r 1remainder not 0test 317 ÷ 3 = 5 r 2remainder not 017 is prime
primality-test A prime number has exactly two factors: 1 and itself. To check, try dividing by each prime up to the square root. For 17, test 2 and 3. If any trial succeeds (remainder 0), the number is composite. Stop as soon as one works.