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 5Output:
2 3 5 73 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;
}