Bounded Sieve of Eratosthenes.

gistfile1.txt

#include "iostream"
#include "vector"
#include "math.h"

using namespace::std;

inline void generate_sieve(vector<int> &sieve) {

  long long int top = 1000000000;

  int lim, i, count, j, val;

  lim = sqrt(top);

  sieve.push_back(2);
  for (i = 3; i < lim; i++)
    sieve.push_back(i);

  count = sieve.size();
  for (i = 1; i < sieve.size(); i++) {
    val = sieve[i];
    for (j = i + 1; j < count; j++)
      if (sieve[j] % val == 0) {
        sieve.erase(sieve.begin() + j);
        count--;
      }
  }
}

inline void display_primes (vector<int> &sieve, int m, int n) {

  int i, j = 0, flag, cap;

  if (m == 0 || m == 1)
    m = 2;

  flag = 1;
  for (i = m; i <= n; i++) {
    cap = sqrt(i);
    for (j = 0; j < sieve.size(); j++) {
      if (sieve[j] > cap)
        break;
      if (i % sieve[j] == 0 && i != sieve[j]) {
        flag = 0;
        break;
      }
    }

    if (flag) {
      cout << i << endl;
    }

    flag = 1;
  }

  cout << endl;
}

int main () {

  long long int count, i, j, val, m, n, t;

  vector<int> sieve;

  long long int end;

  // Limit bound to 10^9
  generate_sieve(sieve);

  // Number of test cases.
  cin >> t;

  while (t--) {
    // Bounds
    cin >> m >> n;
    display_primes(sieve, m, n);
  }

  return 0;
}