关于#素数字符串#的问题，如何解决？

Question

问题遇到的现象和发生背景

题目描述
我们将素数从小到大依次书写，可以得到一个字符串"23571113⋯"，已知一个数码d(0≤d≤9),求字符串在区间[L,R]之间的多少个d?

输入
第一行是一个整数T(1≤T≤10000)，表示样例的个数。 每个样例是一行， 为3个整数，区间L,R,(1≤L≤R≤1000000)和数码d。 区间从1开始计数。

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

样例输入
2
1 8 1
1 8 4

用代码块功能插入代码

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAXN 160000
#define MAXL 2100000
#define len 1100000 
int coun(char dig[],int d,int l);
int prime[MAXN];
bool check[MAXL];
char digit[len];

int main(){
    int i,j,count,T;
    char str[10];
    memset(check,0,sizeof(check));//利用欧拉筛法进行素数制标
    count=0;
    for(int i=2;i<=MAXL;i++){
           if(!check[i])prime[count++]=i;//将素数i存在prime数组中
          for(int j=0;j<count;j++){
               if(i*prime[j]>MAXL)break;
               check[i*prime[j]]=1;//将合数标记为1,素数仍为0
               if(i%prime[j]==0)break;
        }
    }
    for(i=0;i<=MAXN;i++){//素数字符串
         sprintf(str,"%d",prime[i]);
         strcat(digit,str);
         }    
    scanf("%d",&T);
    while(T--){
        int L,R,d;
        scanf("%d %d %d",&L,&R,&d);
        printf("%d\n",coun(digit,d,R)-coun(digit,d,L));
    }
return 0;
}
int coun(char dig[],int d,int l)//统计一定区间内的字符数
{
    int i,cnt=0;
    for(i=0;i<l;i++){
        if((int)dig[i]==d+48)cnt++;
    }
    return cnt;
}

运行结果及报错内容

结果超时，可能是连接字符串那块太慢，但不知道该如何优化

我想要达到的结果

Answer 1

都预处理了，搞个二维数组，你在素筛里把每一位0-9出现的次数统计一下不就好了。
cnt[1e6+100][10],前缀和一下
这样后面判断直接0（1）操作。
你这种写法 T 是1e4 区间是1e6，遍历一遍不超时才奇怪。