题面
【问题描述】
如果一个正整数只有 1 和它本身两个约数，则称为一个质数（又称素数）。
前几个质数是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · · 。
如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如：2, 3, 5, 7, 23, 37 都是纯质数，而 11, 13, 17, 19, 29, 31 不是纯质数。当然 1, 4, 35 也不是纯质数。
请问，在 1 到 20210605 中，有多少个纯质数？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
思路
首先预处理出目标范围内的质数，再暴力枚举这些质数的每一位页是否为质数，满足条件计数器自增一。
答案： 1903
代码
#include<bits/stdc++.h>
using namespace std;
vector<int> primes;
const int N = 20210605;
bool v[N + 10];
//预处理目标范围内的质数
void pre() {
v[0] = v[1] = true; //不是质数
for (int i = 2; i <= N; ++i) {
if (!v[i]) {
primes.push_back(i);
for (int j = 2; j <= N / i; ++j) v[i * j] = true;
}
}
}
//判断每一位是否为质数
bool check(int x) {
while (x) {
int t = x % 10;
if (v[t]) return false;
x /= 10;
}
return true;
}
int main() {
pre();
int ans = 0;
for (int i = 0; i < primes.size(); i++) {
if (check(primes[i])) ans++;
}
cout << ans << endl;
return 0;
}
| 标题： | 2021第十二届蓝桥杯国赛-B纯质数 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/98 |
| 更新： | 2022-09-18 22:38:36 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |