7月21日　「超级素数」是指一个素数，每去掉最后一位数字，剩…

先读懂「超级素数」：它自己是素数，而且每砍掉最后一位、剩下的还是素数（如 373→37→3 一路都是素数）。

【先用最老实的办法：从 2 到 n 一个一个查】
最直接的想法，就是把 2 到 n 每个数都揪出来问一句：你是超级素数吗？怎么问？先看它本身是不是素数；是的话就砍掉末位再看，一路砍到只剩一位，中间只要有一步不是素数，它就不算；全程都是素数，才数它一个。

#include <bits/stdc++.h>
using namespace std;

bool isP(long x) {                 // 判断 x 是不是素数
  if (x < 2) return false;
  for (long i = 2; i * i <= x; i++)
    if (x % i == 0) return false;
  return true;
}

bool isSuper(long x) {             // 每砍掉一位，剩下的都要是素数
  while (x > 0) {
    if (!isP(x)) return false;
    x /= 10;
  }
  return true;
}

int main() {
  long n;
  cin >> n;
  int cnt = 0;
  for (long x = 2; x <= n; x++)
    if (isSuper(x)) cnt++;
  cout << cnt << endl;
  return 0;
}

这个写法好懂也不会错：n=30 数出 6 个，n=50 数出 8 个，样例都对。它只有一个短处——题目里 n 能到一亿，真从 2 查到一亿，太慢了。

【再用一个更快更巧的办法：构造法，一位一位长出来】
关键点：一个多位的超级素数，砍掉末位就是一个更短的超级素数。反过来说，任何超级素数，都是在某个更短的超级素数后面「接一位数字」得到的。于是不必大海捞针，从小往大搭就行：
① 一位的超级素数就是 2、3、5、7；
② 在每个已知的超级素数后面试着接一位（末位只可能是 1/3/7/9，别的末位一定不是素数），接出来若 ≤n 且是素数，它就又是一个新的超级素数；……

看此题详解，练更多题目，进入蓝桥题库每日一练 →

此答案或解析由 AI 生成，请谨慎使用。
难度依赛考组别及等考级别粗略评估，仅供参考。