title: Find numbers that have no primes in their vicinity
body: <p>Let's assume I have a positive integer <em>N</em>. It is said to be <strong>Lonely</strong> if there are no prime numbers from <em>N-k</em> to <em>N+k</em>, where <em>k</em> is a positive integer smaller than <em>N</em>.</p>
  <p>Given two integers <em>L</em> and <em>H</em>, how many <strong>Lonely</strong> integers are there between this range <em>[L,H]</em> (both inclusive).</p>
  <p>I have assumed that <em>k&lt;=L&lt;=H&lt;=100000</em>.
  It is given that if <em>L=3480</em> and <em>H=3750</em>, the output is 2. (The 2 Lonely numbers are 3480 and 3750)</p>
  <p>What I have done until now is first implemented a segmented sieve using the following code:</p>
  <pre><code>import math
  
  def fillPrimes(chprime, high):
    ck = [True]*(high+1)
    l = int(math.sqrt(high))
    for i in range(2, l+1):
      if ck[i]:
        for j in range(i*i, l+1, i):
          ck[j] = False
          
    for k in range(2, l+1):
      if ck[k]:
        chprime.append(k)
  
  def segmentedSieve(low, high):
    chprime = list()
    fillPrimes(chprime, high)
    prime = [True] * (high-low + 1)
    for i in chprime:
      lower = (low//i)
      if lower &lt;= 1:
        lower = i+i
      elif (low % i) != 0:
        lower = (lower * i) + i
      else:
        lower = lower*i
      for j in range(lower, high+1, i):
        prime[j-low] = False
    
    for k in range(low, high + 1):
      if prime[k-low] and k&gt;1:
        prime_list.append(k)
  
  low = 3480
  high = 3750
  k = 10
  prime_list = []
  print(&quot;\nPrimes in Range %d to %d are&quot;%(low,high))
  segmentedSieve(low-k, high+k)
  print(prime_list)
  </code></pre>
  <p>And then <em>tried</em> to implement a binary search on that list to find if there are any primes between N-k and N+k.</p>
  <pre><code>def left(prime_list, num): 
      start = 0; 
      end = len(prime_list)-1; 
      ans = -1; 
      while (start &lt;= end): 
          mid = (start + end) // 2; 
          if (prime_list[mid] &gt;= (num-k)): 
              end = mid - 1; 
          else: 
              ans = mid; 
              start = mid + 1; 
      print(ans)
      return ans;
  
  def right(prime_list, num):
      start = 0;
      end = len(prime_list)-1;
      ans = -1;
      while (start &lt;= end):
          mid = (start + end) // 2;
          if (prime_list[mid] &lt;= (num+k)):
              start = mid + 1;
          else:
              ans = mid;
              end = mid - 1;
      print(ans)
      return ans;
  
  num = 3481
  k = 10
  ##if left(prime_list, num) != -1:
  print(prime_list[left(prime_list, num)])
  ##if right(prime_list, num) != -1:
  print(prime_list[right(prime_list, num)])
  </code></pre>
  <p>And this is where I hit a mental block.</p>
  <p>My errors range from the fact that I am returning the primes shifted by one place in the array, which isn't a big deal, but I am getting errors that I cannot wrap my head around when I start to reach H. (when I receive negative numbers in <em>ans</em>, It starts to read the array from the end, as python likes to do.)</p>
  <p>Any help/thoughts?</p>
  <p><strong>EDIT:</strong>
  If we calculate the difference between two consecutive primes and they differ by more than 2k+1, we'll increment the number of Lonely numbers by the difference of the prime gap and 2k+1. This eliminates the need for the second part of the code.</p>