Below is given code. I have tried vectors as well as array using new to use heap memory for large size.
However, I still get a runtime error. Any quick help will be appreciated. This code runs fine obviously for upper limit<=10000. However, in the question the upper limit is 10^6, I have tried the check prime logic as well, it gives TLE on 1st test case.
#include<bits/stdc++.h>
const int sizearr = 10000;
using namespace std;
int main(void){
int n;
cin>>n;
bool arr[sizearr];
for(int i=0;i<sizearr;i++){
arr[i] = true;
}
arr[0] = false;
arr[1] = false;
for(int i=2;i<sizearr;i++){
if(arr[i] == false){
continue;
}
for(int j=i*i;j<sizearr;j+=i){
arr[j]=false;
}
}
int arr1[sizearr];
arr1[0] = 0;
for(int i=1;i<sizearr;i++){
if(arr[i]==true){
arr1[i] = arr1[i-1]+1;
continue;
}
arr1[i] = arr1[i-1];
}
//delete []arr;
/for(int i=0;i<sizearr;i++){
cout<<arr1[i]<<" ";
}
cout<<endl;/
while(n–){
int left,right;
cin>>left>>right;
cout<<arr1[right] - arr1[left-1]<<endl;
}
//delete []arr1;
}