HDU4548美素数——筛选法与空间换时间
对于数论的学习比较的碎片化，所以开了一篇随笔来记录一下学习中遇到的一些坑，主要通过题目来讲解
本题围绕：素数筛选法与空间换时间
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。HDU4548美素数
题目描述
小明对数的研究比较热爱，一谈到数，脑子里就涌现出好多数的问题，今天，小明想考考你对素数的认识。
问题是这样的：一个十进制数，如果是素数，而且它的各位数字和也是素数，则称之为“美素数”，如29，本身是素数，而且2+9 = 11也是素数，所以它是美素数。
给定一个区间，你能计算出这个区间内有多少个美素数吗？
输入
第一行输入一个正整数T，表示总共有T组数据(T <= 10000)。
接下来共T行，每行输入两个整数L，R(1<= L <= R <= 1000000)，表示区间的左值和右值。
输出
对于每组数据，先输出Case数，然后输出区间内美素数的个数（包括端点值L,R）。
每组数据占一行，具体输出格式参见样例。
样例输入
3
1 100
2 2
3 19
样例输出
Case #1: 14
Case #2: 1
Case #3: 4
题目分析
对于本题，我们容易想到的是先计算出1~1000000之间的所有的素数，但是只是这样还不够，我们需要将空间换时间用到极致才可以，利用一个辅助数组b存放i的各个数位的和，辅助数组c存放前缀为i时包含的美素数个数，在初始化时就完成了所有的计算工作，最后直接输入两个边界数，将两个前缀数组相减即可，详情见代码
代码：
1 #include<iostream> 2 using namespace std; 3 4 const int N = 1000005; 5 int a[N] = {0}; //统计素数 6 int b[N] = {0}; //统计各个位的和 7 int c[N] = {0}; //统计前i个中美素数的个数 8 int cnt; 9 10 void init(){ 11 a[1] = 1; 12 for(int i = 2; i*i <= N; i++){ //素数筛选法 13 if(a[i] == 1) continue; 14 for(int j = 2*i; j <= N; j += i){ 15 a[j] = 1; 16 } 17 } 18 b[1] = 1; 19 for(int j = 2; j <= N; j++){ 20 if(j % 10 == 0){ //如果末尾为0，则要知道j-1的末尾有多少个9才能知道要减去多少，这一部分比较巧妙，会快一些 21 int m = j-1; 22 int s = 0; 23 while(true){ 24 int x = m % 10; 25 if(x == 9){ 26 s++; 27 m /= 10; 28 }else break; 29 } 30 b[j] = b[j-1] - s*9 + 1; 31 }else{ //末尾不为0则各个数位的和为前一个数 + 1 ，比较巧妙，减少了一些计算的时间 32 b[j] = b[j-1] + 1; 33 } 34 } 35 c[1] = 0; 36 for(int i = 2; i <= N; i++){ 37 if(a[i] == 0 && a[b[i]] == 0) c[i] = c[i-1] + 1; 38 else c[i] = c[i-1]; 39 } 40 cnt = 1; 41 } 42 43 int main(){ 44 init(); 45 int t; 46 scanf("%d", &t); 47 while(t--){ 48 int l, r; 49 scanf("%d%d", &l, &r); 50 int add = 0; 51 if(a[l] == 0 && a[b[l]] == 0) add = 1; //这一步需要思考一下，对于两个边界，左边界如果也是美素数则需要 + 1 52 printf("Case #%d: %d\n", cnt++, c[r] - c[l] + add); 53 } 54 return 0; 55 }
更多精彩
