title: Find number of special numbers in a given range
body: <p>I am not able to reduce the complexity of this problem. Please give some better approach.</p>
  
  <p>Is there a mathematical formula that i am not aware of or it can be done with better approach?  </p>
  
  <p><a href="http://www.hackerearth.com/adobe-hiring-challenge/algorithm/game-of-numbers-7/" rel="nofollow">Problem Link</a></p>
  
  <p><strong>Description:</strong></p>
  
  <pre><code> A special number is not divisible by any number of the form Z*Z where (Z&gt;1).
  </code></pre>
  
  <p><strong>Problem</strong>: Find the number of special numbers in a given range.</p>
  
  <p><code>Integer Limit:10^9</code></p>
  
  <p>I have done it like this:</p>
  
  <pre><code>    import math
      def special(x):
          flag=1
          i=2
          if(x==0 or x==1 or x==2):
              return 1
          while(i*i &lt;= x):               //This is the best i can think to limit the numbers.
              if(x%(i*i)==0):
                  flag=0
                  break
              i=i+1
          return flag
  
      t=int(raw_input())
      while(t):
          x,y=map(int,raw_input().split())
          count=0
          for i in xrange(x,y+1):
              if(special(i)):
                  count+=1
          print(count)
          t=t-1
  </code></pre>