做网站 图片更好看,网站开发大体流程图,泰安微信网站制作,利用建站系统wordpress建设网站什么是可截素数#xff1f;
它本身是一个素数#xff0c;如果从左往右逐一截去数字#xff0c;剩下的仍然都是素数#xff0c;如果从右往左逐一截去数字#xff0c;剩下的也仍然都是素数。
例如#xff1a;3797就是一个可截素数。
从左往右截去数字#xff1a;797
它本身是一个素数如果从左往右逐一截去数字剩下的仍然都是素数如果从右往左逐一截去数字剩下的也仍然都是素数。
例如3797就是一个可截素数。
从左往右截去数字797977 都是素数
从右往左截去数字379373 都是素数。 题目求前11个可截素数的和。注2357 不是可截素数 题目解析
这个题目依然是对素数的处理对于这种对连续且大量的数据进行素数的判断的问题我们可以使用素筛法或线性筛法来获得素数表。由于素筛法的时间复杂度是O(log(log(n))) 而线筛法的时间复杂度可以达到O(n), 当数据规模不大时二者的程序运行效率的差异是不明显的但当数据规模非常庞大的时候线筛法更优。
所以第一步构建素数表。
第二步遍历素数表判断当前素数值是否满足可截素数的特点。
可截素数的特点就是从左到右和从右到左截去数据所得数值依然是素数。 从左到右截去数字 以3797为例 3797 797 97 7 可见从左往右截去数字就是一个不断去掉最高位的过程。如何去掉一个数N的最高位用 N 对其最高位的权重 取模。 3797 的最高位是33的权重是1000 所以 3797 797 这个截去3的操作就是 3797 % 1000 797的最高位是77的权重是100所以797 97 就是 797 %100 97 的最高位是99的权重是10所以97 7 就是97 % 10 7已经是个位数截去操作结束。 2. 从右往左截去数字 依然以3797为例3797 379 37 3 从右往左截去数字就是一个不断去掉最低位的过程。截掉最低位就是数字规模缩小10倍即 N /10
代码实现
#include stdio.h
#include math.h#define MAX_N 2000000int prime[MAX_N5] {0}; //从prime[1]开始存放素数 prime[0]表示prime数组中素数总个数
int is_prime[MAX_N5] {1,1,0}; //用于标记是否为素数如果i为素数则is_prime[i] 0,否则is_prime[i] 1;//利用线性筛法构建素数表
void init_prime(){for(int i 2;i MAX_N;i){if(!is_prime[i]) prime[prime[0]] i; //is_prime[i] 0, 表示数字i为素数存入primefor(int j 1; j prime[0];j){if(prime[j] * i MAX_N) break;is_prime[prime[j] * i] 1;if(i % prime[j] 0) break;}}return;
}//将当前素数n执行从左到右截去和从右到左截去后如果依然是素数返回1否则返回0
int is_val(int n){int digit floor(log10(n)); //求n的位数int temp n;//从左向右截去数字for(int i digit; i 0;i--){if(is_prime[temp % (int)pow(10,i)]) return 0;}//从右向左截去数字for(int i 1 i digit; i){if(is_prime[temp / (int)pow(10,i)]); return 0;}return 1;
}int main(){init_prime();int flag 11;long long sum 0;for(int i 1; i prime[0];i){if(prime[i] 10 is_val(prime[i])){sum prime[i];if(--flag 0) break;}}printf(sum %d\n,sum);return 0;
}
代码优化
int is_val(int n){//从左往右截去int h pow(10,floor(log10(n)))temp n;while(n){if(is_prime[n]) return 0;n % h;h / 10;}//从右往左截去while(temp){if(is_prime[temp]) return 0;temp / 10;}return 1;
}
