/*
 
     NOTE: CODE UPDATED 12-5-14 
 
 Name: Brian Butler
 Professor: Gary Hartell
 Date: September 22, 2011
 Assignment: Sieve of Sundaram
 
                             Descripion:
    This program uses the Sieve of Sundaram to find all of the prime numbers up to
    and including the integer entered by the user.
 
                Algorithm:(taken from Wikipedia.com)
 
  Start with a list of the integers from 1 to n. From this list, remove all
  numbers of the form i + j + 2ij where:
 
   1)   i,j Elements of N, 1<= i<=j
   2)   i + j + 2ij <= n
 
 The remaining numbers are doubled and incremented by one, giving a list of the
 odd prime numbers (i.e., all primes except the only even prime 2) below 2n + 2.
 
 The sieve of Sundaram is equivalent to the sieve of Eratosthenes, except that
 the initial list corresponds only to the odd integers; the work of "crossing out"
 the multiples of 2 is done by the final double-and-increment step.
 Whenever Eratosthenes' method would cross out k different multiples of a prime 2i+1,
 Sundaram's method crosses out i + j(2i+1) for i <= j <= ( inputNumber / 2).
 
 
                  CALCULATIONS BELOW ARE TAKEN FROM:
                http://en.wikipedia.org/wiki/Sieve_of_Sundaram
*/
 
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

struct my_bounds {
    int lower;
    int higher;
};
 
int main()
{ 
    int cases = 0;                            // number of cases
    const double highest_bound = 1000000000;  // max number from user input
    double square_root = 0.0;                 // square root for the highest_bound
    int upper_bound = 0;                      // upper bound for calculations
   
    vector<int> primes;    // array of prime numbers
    vector<int> temp;      // array for prime numbers that are inside given bounds
    
    // Save number of cases into the memory and create set of bounds
    cin >> cases;           // store the number of cases
    my_bounds *bp[cases];   // array of pointers to use structures
    
    for (int i = 0; i < cases; i++) {
        bp[i] = new my_bounds;      // allocate memory for structures
        
        cin >> bp[i]->lower;        // store user input using these structures
        cin >> bp[i]->higher;
    }

    // CALCULATIONS BELOW ARE TAKEN FROM:
    // http://en.wikipedia.org/wiki/Sieve_of_Sundaram
 
    // precompute all primes smaller than sqrt(highest_bound)
    square_root = sqrt(highest_bound);
    square_root = ceil(square_root);
    upper_bound = int(square_root);
    
    // Fill the array with initial numbers (1, 2, ..., sqrt(highest_bound))
    for (int i = 0; i < upper_bound; i++)
    {
        primes.push_back(i + 1);
    }
    
    int n = upper_bound / 2; // ? find the midpoint   
    int totalPrimes = 0;     // variable for the total number of prime numbers 
                             //  that are found
    int TheseArePrime = 0;   // variable used in the array that stores the prime
                             //  numbers found
    
    for (int i = 1; i < n; i++)
    {
        for (int j = i;  j<= (n-i)/(2*i+1); j++)
        {
           primes[i + j + 2 * i * j] = 0;     /*From this list, remove all
                                                 numbers of the form i + j + 2ij    */
        }
    }
    
    if (upper_bound >= 2)
    {
        primes[TheseArePrime++] = 2; /* this IF statement adds 2 to the output 
                                      * since 2 is a prime number    */
        totalPrimes++;
    }

    for (int i = 1; i < n; i++)
    {
        if (primes[i] != 0)
        {
            primes[TheseArePrime++]=i*2+1;
                                                /*The remaining numbers are
                                                doubled and incremented by
                                                one, giving a list of the
                                                odd prime numbers (i.e., all
                                                primes except the only even
                                                prime 2) below 2n + 2.  
                                                 */

            totalPrimes++;// the counter of the number of primes found
        }
    }
 
    
    int lower = 0;          // current lower limit
    int higher = 0;         // current higher limit
    int found_primes = 0;   // how much primes are found
    bool is_prime = true;   // flag that shows if the current number is prime
        
    
    for (int i = 0; i < cases; i++) {
        // initialize variables
        lower = bp[i]->lower;
        higher = bp[i]->higher;
        found_primes = 0;
        temp.clear();
        
        if (higher <= primes.back()) {
            /* Output numbers in given bounds from array with found primes */
            for (int x = 0; primes[x] <= higher ; x++) {
                if (primes[x] >= lower) {
                    cout << primes[x] << endl;
                }
            }
        } else {
            /* Create an array of primes inside given bounds */
            for (int j = lower; j <= higher; j++)
            {
                is_prime = true;
                for (int k = 0; k < totalPrimes; k++) {
                    if ( (j % primes[k]) == 0 ) { // Divide current number with
                                                  // all previous primes
                        is_prime = false;
                        break;
                    }
                }
                // Add found element to the array
                if (is_prime) {
                    temp.push_back(j);
                    found_primes++;
                }
            }
            // Output found numbers in the given range
            for (int x = 0; x < found_primes; x++) {
                cout << temp[x] << endl;
            }
        }
        
        cout << endl;        
    }
    
    for (int i = 0; i < cases; i++) {
        delete bp[i];                       // free the memory
    }

    return 0;
}