关于超时的问题，如何解决？

Interprime
题目描述
n是两个连续的奇素数的平均值，且n不是素数，那么我们称这样的数是"内部素数"。求区间[a,b]内"内部素数"的个数。比如，前5个"内部素数"是4,6,9,12,15。

输入
第一行是样例数T(1≤T≤1000)。 每个样例一行，为三个整数a,b(1≤a≤b≤106)。

输出
每行输出一个样例的结果。

样例输入
5
1 10
1 100
1 1000
1 10000
1 100000
样例输出
3
24
166
1228
9591

问题：我该如何优化这个代码，现在是超时了的
时间要求是1s,空间要求不需要管

//连续的（奇数&&素数）/2=一个内部素数==下标，其值为1
//SUM【】是前缀和
#include <bits/stdc++.h>
using namespace std;
int no_prime[1000001]={0};
int sum[1000001]={0};
int interprime[1000001]={0};
int jiprime[1000001]={0};
int main(){
    int t;
    cin>>t;
    no_prime[0]=no_prime[1]=1;
    int i,j;
    for(i=2;i<1000001;i++)
        if(!no_prime[i])
            for(j=i*2;j<1000001;j+=i)
                no_prime[j]=1;
    //打素数表
    for(i=1;i<1000001;i+=2)
        if(!no_prime[i]) jiprime[i]=1;
    //内部素数表
    for(i=1;i<1000001;i+=2){
        for(j=i+2;j<1000001;j+=2){
            if(jiprime[i]&&jiprime[j]){
                interprime[(i+j)/2]=1;
                break;//保证连续,一有就跳出
            }
        }
    }
    sum[3]=sum[2]=sum[1]=0;
    for(i=4;i<1000001;i++){
        sum[i]+=sum[i-1]+interprime[i];
    }
    
    while(t--){
        int a,b;
        cin>>a>>b;
        cout<<sum[b]-sum[a-1]<<endl;
    }
    
    return 0;
    
}