title: Optimizating Prime Number Sequence
body: <p>I am stuck on a questions from Codechef practice problems difficulty medium with problem statement:</p>
  
  <blockquote>
    <p>Shridhar wants to generate some prime numbers for his cryptosystem.
    Help him! Your task is to generate all prime numbers between two given
    numbers</p>
  </blockquote>
  
  <p><a href="https://www.codechef.com/problems/PRIME1" rel="nofollow noreferrer">Rest of the description, I/O format, Test cases examples on this question link</a></p>
  
  <p>The problem with my implementation is getting a TLE (Time Limit Exceeded) and wish to solve this problem, can you point out any problem in my implementation, I can't seem to figure it out after hours of dry run.</p>
  
  <p>Includes, Directives and ifPrime function</p>
  
  <pre><code>#include&lt;map&gt;
  #include&lt;math.h&gt;
  #include&lt;stdio.h&gt;
  #define LLD long long int
  #define REPNE(i,a,b) for(LLD i=a; i&lt;=b; ++i)
  #define REPNEI(i,a,b,k) for(LLD i=a; i&lt;=b; i+=k)
  using namespace std;
  
  map&lt;LLD, bool&gt; mem;
  
  bool ifPrime ( LLD a ) {
      if ( a&lt;2 ) return false;
      else if ( a==2 ) return true;
      else if ( a%2==0 ) return false;
  
      REPNEI(i,3,sqrt(a),2) {
          if ( a%i==0 ) return false;
      }
  
      mem[a] = true;
      return true;
  }
  </code></pre>
  
  <p>Generate Prime Function</p>
  
  <pre><code>void genPrime ( LLD a, LLD b ) {
      REPNE(i,a,b) {
          if ( mem.find(i) != mem.end() ) printf("%lld\n", i);
          else if ( ifPrime(i) ) printf("%lld\n", i);
      } printf("\n");
  }
  </code></pre>
  
  <p>Main</p>
  
  <pre><code>int main ( ) {
      // freopen("input.txt", "r", stdin);
  
      int t; scanf("%d", &amp;t);
      REPNE(test, 1, t) {
          LLD a, b;
          scanf("%lld %lld", &amp;a, &amp;b);
  
          genPrime(a,b);
  
      }
  } 
  </code></pre>
  
  <p>I can't think of another solution to this problem, the only way I came up is memoization, and it is also handling large integers as well. Help needed.</p>