Determine if number is prime

[adm45]

What is the underlying rule or concept that MGMAT is trying to tell us here with its solutions and how important is it that we remember this rule/concept (see below)? Also, in your answer can you provide example with different numbers. Thank you very much!

We are told that to determine if numbers (for example 61 and 67) are prime we only need to check if it is divisible by up to the square root of the number in question. The square root of 61 and the square root of 67 are around 8 so we only have to check that 7 does not go into either 61 or 67; it does not. Thus 61 and 67 are prime numbers.

[jlucero]

Let's start with a simpler example. The factors of 30 are:
1 x 30
2 x 15
3 x 10
5 x 6

Notice that this pattern gets us to "numbers in the middle". I can stop with 5 x 6, because if 11 were a prime factor of 30, I would have counted it on the right side of my factors. Similarly, you can test for prime factors of larger numbers by starting at the lowest prime factor and work towards "numbers in the middle". Let's do 67:

2 x 33.5 (not a factor)
3 x 22ish (not a factor)
5 x 13ish (not a factor)
7 x 9ish (not a factor)

And I'm done. If I continued this to larger prime factors, the number on the right would have been a smaller factor I already tested.

11 x 6ish.

Basically, we already determined numbers less than 8 were not factors, so any numbers that are greater than 8 would already have been accounted for.