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&lt;=10). In each of the next t lines there are two numbers m and n (1
  &lt;= m &lt;= n &lt;= 1000000000, n-m&lt;=100000) separated by a space.
  
  Output
  
  For every test case print all prime numbers p such that m &lt;= p &lt;= 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 &lt;iostream&gt;
#include &lt;stdlib.h&gt;
#include &lt;vector&gt;
#include &lt;math.h&gt;

using namespace std;

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

// Functions
std::vector&lt;input&gt; parseInput();
void printPrimes(std::vector&lt;bool&gt; primes , bignum start , bignum end);
std::vector&lt;bool&gt; findPrimes(bignum start , bignum end);

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

    std::vector&lt;bool&gt; primes;
    std::vector&lt;input&gt; programInput;

    programInput = parseInput();

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

// Parse Input as an Array
std::vector&lt;input&gt; parseInput(){
    int testCases;
    bignum start;
    bignum end;

    cin &gt;&gt; testCases;

    std::vector&lt;input&gt; parsedInput(testCases);
    input currentInput;

    for (int i = 0; i &lt; testCases; ++i){
        cin &gt;&gt; start &gt;&gt; end;
        currentInput = {start , end};
        parsedInput.push_back(currentInput);
    }

    return parsedInput;
}

// Print all the Primes
void printPrimes(std::vector&lt;bool&gt; primes , bignum start , bignum end){
    for (int i = start; i &lt;= end; ++i){
        if (primes[i] == true){
            cout &lt;&lt; i &lt;&lt; '\n';
        }
    }
}

// Find all Prime Numbers between two numbers
std::vector&lt;bool&gt; findPrimes( bignum start , bignum end){

    // Define an array of Bits and Set all Bits to 1
    std::vector&lt;bool&gt; primeSeive(end);

    // Assign all Numbers upto end as True
    primeSeive.assign(end + 1, true);

    // 0 and 1 is not a prime
    primeSeive[0] = false;
    primeSeive[1] = false;

    for (int i = 2; i &lt;= end ; ++i ){
        for (int j = 2; j &lt;= (end / i); ++j){
            primeSeive[i*j] = false;
        }
    }

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

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

    std::vector&lt;bool&gt; primes;
    std::vector&lt;input&gt; programInput;

    programInput = parseInput();

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

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


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