title: To find a number is prime, Why checking till n/2 is better. What is the reason for avoiding numbres in second half of n
body: <p>To check if a number is prime or not, the naive way is to try dividing the number by 2 thru n, and if any operation gets remainder as 0, then we say the given number is not prime.
  But its optimal to divide and check only till n/2 (am aware much better way is till sqrt(n) ), I want to know the reason for skipping the second half.</p>
  
  <p>say if we need to check number 11 is prime or not, 
  11/2 = 5.
  if we do 11/6 or 11/7 or 11/8 or 11/9 or 11/10 in neither of these cases we get remainder as 0. 
  So is the case for any given number n.</p>
  
  <p>Is the reason for avoiding second half this? "if you divide the given number by any number which is more than given number's half, remainder will never be 0 Or in other words, none of the numbers which are more than the given number's half can divide the given number"</p>
  
  <p>Please help me know if am right</p>