Find All the Primes Between two Numbers

I wrote a solution to the Coding Challenge SPOJ Prime in C++ using the Sieve of Eratosthenes. How much Ever I tried I could not get over the Time Limit on SPOJ which is 6s for Primes upto 1000000000.

Here is the Problem StateMent


Input


The input begins with the number t of test cases in a single line
(t<=10). In each of the next t lines there are two numbers m and n (1
<= m <= n <= 1000000000, n-m<=100000) separated by a space.


Output


For every test case print all prime numbers p such that m <= p <= n,
one number per line, test cases separated by an empty line.


Example


Input:

2

1 10

3 5


Output:

2 3 5 7


3 5


Warning: large Input/Output data, be careful with certain
languages (though most should be OK if the algorithm is well designed)

How can I optimise this Code ?

```
/*
* Generate Prime Numbers Between two given numbers.

* Url : http://www.spoj.com/problems/PRIME1/
* Dated : 16-Jun-2016

* Performance Oriented , that's why I'm using C++. The AlgoRythm is the Famous Seive of Euractus
*/

#include
#include
#include
#include

using namespace std;

typedef long int bignum;
struct input {
bignum start;
bignum end;
};

// Functions
std::vector parseInput();
void printPrimes(std::vector primes , bignum start , bignum end);
std::vector findPrimes(bignum start , bignum end);

int main(){
system("clear");

std::vector primes;
std::vector programInput;

programInput = parseInput();

for (int i = 0; i parseInput(){
int testCases;
bignum start;
bignum end;

cin >> testCases;

std::vector parsedInput(testCases);
input currentInput;

for (int i = 0; i > start >> end;
currentInput = {start , end};
parsedInput.push_back(currentInput);
}

return parsedInput;
}

// Print all the Primes
void printPrimes(std::vector primes , bignum start , bignum end){
for (int i = start; i findPrimes( bignum start , bign

Just do the sieve once, this should give you about 5-10x increase.

int main(){
    system("clear");

    std::vector primes;
    std::vector programInput;

    programInput = parseInput();

    auto maxPrime = programInput.begin()->end;
    for(auto& m : programInput){
         maxPrime = max(maxPrime, m.end);
    }
    primes = findPrimes(0, maxPrime);

    for (int i = 0; i < programInput.size(); ++i){
        printPrimes(primes , programInput[i].start, programInput[i].end);
    }
}

Then avoid the vector copies by taking all vector parameters by const & and you should be golden.

StackExchange Code Review Q#132143, answer score: 2