A simple explanation of how the 2 through sqrt of n prime number test works(hardforkit.com)
hardforkit.com
A simple explanation of how the 2 through sqrt of n prime number test works
http://hardforkit.com/2016/01/14/How-The-Two-Through-Square-Root-Of-N-Prime-Number-Test-Works.html
If a number N is composite, then it is a product of two numbers smaller than N. Let's call them n1 and n2.
If both n1 and n2 are greater than sqrt(N), then their product would exceed N, violating the assumption above that they equal N:
N= sqrt(N) x sqrt(N) < n1 x n2
A similar argument applies if both n1 and n2 are smaller than sqrt(N): n1 x n2 is less than N, violating the assumption.
So the only other possibilities are:
a) n1 and n2 are exactly equal to sqrt(N)
b) one of the factors is less than sqrt(N) and the other is greater than sqrt(N)
So if either n1 or n2 are not exactly equal to sqrt(N), then a composite number N must have at least one factor less than sqrt(N).