title: Count of Coprimes for each number
body: <p>I recently came across this question in a hiring challenge :</p>
  
  <p>Given an interval [L, R] (1 &lt;= L,R &lt;= 10^5), we need to tell number of coprimes of K in interval [L, R] for each K in [L, R].</p>
  
  <p>e.g. L = 3, R = 7</p>
  
  <p>for K = 3, number of coprimes in [3, 7] = 3 (4, 5, 7)</p>
  
  <p>for K = 4, number of coprimes in [3, 7] = 3 (3, 5, 7)</p>
  
  <p>for K = 5, number of coprimes in [3, 7] = 4 (3, 4, 6, 7)</p>
  
  <p>...</p>
  
  <p>By my approach, I am finding prime numbers upto R and then for each K, by its prime factors, counting number of coprimes, but I need better and efficient approach than this. Thanks in advance.</p>