This is the simplest test for distinguishing prime numbers from others. It simply tries if the number is divisible by any number in the range between 2 and a square root. If it is - number is composite, otherwise it's prime. We can assume that if the number is composite, then there will be its divider in tested range, because divisor's of a number are in pairs, which in multiplication give the input number. Therefore at least one of the numbers in pair must be less or equal to square root. The test have complexity o(sqrt(p)) so it's not very efficient and can be applied only to numbers in the range of longint.

To see source code click here.

To see that it really works, use below: