Hi,

I hope someone can help.

I am trying to developed an algorithm which based on a given input, call it x, determines whether x is prime.

One way to do this is to check all the numbers (starting at 2) up to x/2 is divisible by x. If there is such a number, then x is not prime. I understand this strategy completely.

However, another way to to check all numbers (starting at 2) up to the square root of x. Can someone please explain to be why this works?