©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>Description
素数字符串
<>题目描述
我们将素数从小到大依次书写，可以得到一个字符串"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
<>样例输出
3
0
话不多说，直接上代码！
#include <stdio.h>//终于AC了^*^ #include <string.h> #include <stdbool.h> int prime
[160000];//按顺序存储素数(从1开始) bool check[2100000];//检查素数 int time[11][1100000];
//存储数字0~9出现的次数 int main() { int i, j, D, cnt = 0, ordNum = 1; char str[10];
memset(check, 0, sizeof(check)); memset(time, 0, sizeof(time)); for (i = 2; i <
2100000; i++) {//欧拉筛法（不理解的同学可以去C一下） if (!check[i])prime[ordNum++] = i;
//将素数i存在prime数组中(ordNum表示序数) for (j = 1; j < ordNum; j++) { if (i * prime[j] >
2100000)break;//越界退出! check[i * prime[j]] = 1;//将非素数标记为1,素数仍为0(任何数的最小质因数都是确定的)
if (i % prime[j] == 0)break;//筛过一次的不用再重筛! } } for (i = 1; prime[i] != 0; i++) {
memset(str, '\0', sizeof(str)); sprintf(str, "%d", prime[i]);
//sprintf函数可以将int型整数转为int型数组 for (j = 0; str[j] != '\0'; j++) { for (D = 0; D <=
9; D++) { if (str[j] == (char)(D + 48))time[D][cnt + j + 1] = 1;//'0'的ASCII码是48
} } cnt += strlen(str); } for (D = 0; D <= 9; D++) { for (i = 2; i <= 1000000; i
++) { time[D][i] += time[D][i - 1];//前缀和 } } int T, L, R, d; scanf_s("%d", &T);
while (T--) {//不要将上面的素数打表和求前缀和放到循环里，不然TLE到怀疑人生QAQ scanf_s("%d %d %d", &L, &R, &d
); printf("%d\n", time[d][R] - time[d][L - 1]); } return 0; }