EDIT: was able to identify the fault (still didn’t fix the whole thing, so not sure), but the I increment the i inside the loop, which should cause some false primevectors, not sure how it worked on my terminal though
After trying to implement the sieve of eratosthenes and finally get it right (at least I think I did), the SPOJ result is time limit exceeded, tried to execute it in ideone to see how much time it takes, ideone prints incorrect output, not sure what’s happening?
And this is what my terminal prints after execution and providing the same input
2
3
5
7
[There is an extra line here]
3
5
Code:
#include <iostream>
#include <string>
#include <sstream>
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;
void findPrimes(int min,int max){
if(min == 1)
min++;
int vectorsize = int(sqrt(max-1));
vector<bool> primesVector(vectorsize,true);
int arrSize = max-min+1;
bool mArr[arrSize];
for(int i=0;i<vectorsize;i++){
if(primesVector[i] == true){
i += i+2;
while(i<vectorsize){
primesVector[i] = false;
i += i+2;
}
}
}
for(int i=0;i<vectorsize;i++){
if(primesVector[i]){
for(int j=0;j<arrSize;j++){
if((j+min)%(i+2)==0){
if((j+min)==(i+2))
j += i+2;
while(j<arrSize){
mArr[j] = true;
j += i+2;
}
}
}
}
}
for(int j=0;j<arrSize;j++){
if(mArr[j] == false)
cout << j+min << endl;
}
}
int main () {
int n;
cin >> n;
for(int i=0;i<n;i++){
int min, max;
cin >> min >> max;
findPrimes(min,max);
if(i<n-1)
cout << endl;
}
return 0;
}