Find All the Primes Between two Numbers

Question

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 <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>

using namespace std;

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

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

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

    std::vector<bool> primes;
    std::vector<input> programInput;

    programInput = parseInput();

    for (int i = 0; i < 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<input> parseInput(){
    int testCases;
    bignum start;
    bignum end;

    cin >> testCases;

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

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

    return parsedInput;
}

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

// Find all Prime Numbers between two numbers
std::vector<bool> findPrimes( bignum start , bignum end){

    // Define an array of Bits and Set all Bits to 1
    std::vector<bool> 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 <= end ; ++i ){
        for (int j = 2; j <= (end / i); ++j){
            primeSeive[i*j] = false;
        }
    }

    return primeSeive;
}

Answer 1

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

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

    std::vector<bool> primes;
    std::vector<input> 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.

Answer 2

For a start, try to implement the following declarations.

#include <cmath>     // include C++ header
#include <cstdint>   // avoid "using namespace std"
#include <vector>
#include <utility>

using number = std::uint_fast64_t;

std::pair<number,number> parseInput     ();
std::vector<number>      findPrimesUpTo (number end);
void                     printPrimes    (number start,
                                         std::vector<number> const&primes);

this avoid unnecessary (and costly) copies of vectors and prefers std::pair over a locally defined struct. Also, it merely returns the primes wanted rather than an array of bools (most of which are false).

Second, write the sieve in an efficient way, for example something like

std::vector<number> findPrimes(number end)
{
  std::unique_ptr<bool[]> is_prime(new bool[end]);
  for(number i=0; i!=end; ++i)
    is_prime[i] = true;
  for(number i=2; i*i<=end; ++i)
    if(is_prime[i])
      for(number j=i*i; j<=end; j+=i)
        is_prime[j] = false;
  std::vector<number> primes;
  for(number i=0; i!=end; ++i)
    if(is_prime[i]) primes.push_back(i);
  return primes;
}

which should have complexity O(n log(n) log(n)).

Finally, of course, if doing this for several pairs (start,end), you only need to find the prime numbers for the maximum end once.

Answer 3

If the other solutions don't get you to the required time, the intended solution here is to use a windowed sieve.

const long MAXIMUM_CANDIDATE = 1000000000;

I would declare this as a constant right off. That documents this limitation of the program.

const int WINDOW_SIZE = 100000;

This is MAXIMUM_CANDIDATE with half its zeroes (rounded down) removed. It's larger than the square root but only by a factor of about three or so. Perhaps not coincidentally, it is also the maximum value for n - m given in the problem statement.

You prime this by using a sieve to generate all primes from 2 to WINDOW_SIZE. So your main

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

    std::vector<bool> primes;
    std::vector<input> programInput;

    programInput = parseInput();

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

would become something like

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

    std::vector<bool> primeStatuses = findPrimes(2, WINDOW_SIZE);
    std::set<int> primes = convertSieveToSet(primeStatuses);

    for (auto inputRow : parseInput()) {
        printLongs(findPrimesInRange(primes, inputRow.start, inputRow.end));
    }
}

where printLongs just prints every member of a std::vector<long>.

I changed to the range-based for loop as being simpler. It doesn't matter functionally if you prefer the original. Similarly, you can add more intermediate variables if you want.

The findPrimes function is the same. The convertSieveToSet skims out the non-prime values so that we can just enumerate over the prime values. You might also just use a sorted std::vector instead. I used std::set because it has good time complexity for find operations. But perhaps the overhead of managing the set would overcome that.

The main insight there is that you are better off with just the primes in the data structure rather than constantly iterating over a set of Boolean values where you ignore most of them. Iterate over the std::vector<bool> once to reduce it to a std::vector<int>.

Now we can just mask out any multiples of primes in our windows. That's what the findPrimesInRange function does. It takes a list of possible prime factors and the beginning and end of a range. Both beginning and end must be less than the square of the WINDOW_SIZE (which the problem statement says they will be).

I'll leave it up to you to write findPrimesInRange. If you're looking for a hint, I wrote a Java version here. Another answer to the same question posts a link to a segmented sieve (which is similar) for C++.

Note: when testing, make sure that you try the last window. I.e. 999900000 to 1000000000. For many solutions, this will be the slowest value to generate. As such, it is almost certain to be one of the test cases used by the online judge.