title: Prime numbers which can be written as sum of the squares of two numbers x and y
body: <p>The problem is: </p>
  
  <p>Given a range of numbers <code>(x,y)</code> , Find all the prime numbers(Count only) which are sum of the squares of two numbers, with the restriction that <code>0&lt;=x&lt;y&lt;=2*(10^8)</code> </p>
  
  <p>According to <a href="http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares" rel="nofollow noreferrer">Fermat's theorem</a> :</p>
  
  <pre><code>Fermat's theorem on sums of two squares asserts that an odd prime number p can be   
  expressed as p = x^2 + y^2 with integer x and y if and only if p is congruent to 
  1 (mod4).
  </code></pre>
  
  <p>I have done something like this:</p>
  
  <pre><code>import math
  def is_prime(n):
      if n % 2 == 0 and n &gt; 2:
          return False
      return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))
  
  a,b=map(int,raw_input().split())
  count=0
  for i in range(a,b+1):
      if(is_prime(i) and (i-1)%4==0):
          count+=1
  print(count)
  </code></pre>
  
  <p>But this increases the <em>time complexity</em> and <em>memory limit</em> in some cases.</p>
  
  <p>Here is my submission result:</p>
  
  <p><img src="https://i.stack.imgur.com/0gBur.png" alt="enter image description here"> </p>
  
  <p>Can anyone help me <strong>reduce the Time Complexity and Memory limit with better algorithm</strong>?</p>
  
  <p><a href="http://www.hackerearth.com/problem/algorithm/primeman-1/" rel="nofollow noreferrer">Problem Link</a>(Not an ongoing contest FYI)</p>