So I was trying to attempt this problem, and I tried to implement the Segmented Sieve Algorithm to solve this. My algorithm runs for most cases, the sample test cases and the corner cases, as well as whatever I have tried. However, whenever I try submitting this code, it gives me a SIGSEV error, I tried checking my code and I was not accessing any index that was out of bounds. Also the space complexity of my solution is O(sqrt(n)). Can someone help me understand, where am I going wrong, I have spent more than 6 hours on my solution, but cannot figure out the mistake. Any help would be appreciated.
//http://www.spoj.com/problems/PRIME1/
#include <iostream>
#include <math.h>
#include <vector>
#include <cstdio>
using namespace std;
typedef unsigned long l;
int main(){
ios::sync_with_stdio(false);
int t;
vector<int> v;
vector<long> next;
l m, n;
cin>>t;
for(int test = 0; test < t; test++){
cin>>m>>n;
if(m == 1){
m++;
}
bool a[(int)sqrt(n) + 1];
fill_n(a, (int)sqrt(n) + 1, true);
for(int i = 2; i <= sqrt(sqrt(n)); i++){
if(a[i]){
for(int j = i * i; j <= sqrt(n); j += i){
a[j] = false;
}
}
}
for(int i = 2; i <= (int)sqrt(n) + 1; i++){
if(a[i]){
v.push_back(i);
}
}
int i = (int)((m - 2) / (int)sqrt(n));
for(int j = 0; j < v.size(); j++){
for(int k = 2 + (i * (int)sqrt(n)); k < 2 + ((i + 1) * (int)(sqrt(n))) && k <= n; k++){
if(k % v[j] == 0){
next.push_back(k);
break;
}
}
}
for(int c = i; c <= (int)sqrt(n); c++){
bool a[(int)sqrt(n)];
fill_n(a, (int)sqrt(n), true);
int count = 0;
for(int j = 0; j < v.size(); j++){
l temp = next[count] + v[j];
for(l k = next[count]; k < 2 + ((c + 1) * (int)(sqrt(n))) && k <= n; k += v[j]){
if(k != v[j]){
a[k - (2 + (c * (int)sqrt(n)))] = false;
}
temp = k + v[j];
}
next[count++] = temp;
}
for(int j = 0; j < (int)sqrt(n); j++){
if(a[j] && (2 + (c * (int)sqrt(n)) + j) >= m && (2 + (c * (int)sqrt(n)) + j) <= n){
cout<<2 + (c * (int)sqrt(n)) + j<<"\n";
}
}
}
cout<<"\n";
}
return 0;
}
Please help me understand, where I might be going wrong.