Skill Builder: How to Test Whether a Number is Prime

Prime numbers are very special. A prime number is a number that is divisible evenly only by itself and 1. Hence, 18 is not a prime number because it can be formed as the product of 2 and 9, 3 and 6, or 18 and 1. In other words, it has many factors, other than itself and 1. In contrast, 23 is a prime number because its only factors are 1 and itself, 23.

Some questions on the SHSAT will ask us to determine whether a number is, in fact, prime. To determine whether any given number is prime, we have to try to find its factors.

Here is Question 99 from the Old SHSAT Test #6 that tests our ability to recognize prime numbers.

Example: Question 99. What is the greatest prime factor of 5,355?

A) 17

B) 51

C) 119

D) 131

E) 153

The above question actually has two parts. The first part asks us to figure out which of the choices are, in fact, prime numbers. The second part asks us to find, among those prime numbers, the greatest factor of 5,355.

Solution:

Start out by eliminating choices that aren't prime numbers. Choice B can be eliminated because 51 = 3 x 17. Likewise, Choice C can be eliminated because 119 = 7 x 17. Your number sense will improve as you practice more. You will think of 3 x 7 = 21 whenever you see a 1 in the ones place of a product. And you will think of 7 x 7 =49 whenever you see a 9 in the ones place as a product.

Choice E can be eliminated because 153 is divisible by 3. Indeed, 3 x 51 = 153.

That leaves us with Choices A) 17 and D) 131. We can tell after a few calculations on paper or in our head that 17 is a prime number. But what about 131? It sort of looks like a prime number. But, is there a way to know for certain whether a number is, in fact, prime?

Here is a quick, effective method.

Prime Number Test

1. Compute (or estimate) the square root of the given number.

2. List all prime numbers up to that square root value.

3. Test divisibility only by those prime numbers.

When applied to our example (131), the method looks like this:

1. The square root of 131 is a bit more than 11 because 11 x 11 = 121 and 12 x 12 = 144.

2. The prime numbers up to the square root of 131 (a little more than 11) are: (2, 3, 7, 11)

3. We test whether 131 is divisible by 2, 3, 7, and 11. We quickly see that 131 isn't divisible by 2 or 3. And it also isn't divisible by 7 or 11.

Therefore, we know that 131 is, in fact, a prime number.

Back to our SHSAT Question.

Of the two remaining choices, we know that Choice A) 17 and Choice D) 131 are both prime numbers. To test whether they are in, fact, factors of 5,355, we can do the division. We divide 5,355 by 131 to see if 131 goes into 5,355 evenly. If it does, 131 would be our greatest common factor. If it doesn't, we'd test whether 17 goes into 5,355.

What do you get as the answer? Which number is the greatest prime factor of 5,355?

For more information about this or other SHSAT questions, please contact NYCGPrep at info@nycgprep.com

We have on-going SHSAT classes at our convenient midtown location, close to K-Town, Chelsea, SoHo, and all Manhattan neighborhoods.