前缀素数
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
我们定义一种特殊的数：如果这个数本身是素数，并且去掉它的最后一位数字后剩下的部分仍然是素数（或为空），则称其为“前缀素数”。例如： 素数 293是前缀素数，因为：
293是素数,
去掉末位得 29，是素数,
再去掉末位得 2，是素数,
最后剩下空，停止。
给定一个整数 N(1≤N≤1e6)，请计算区间 [1,N]内有多少个前缀素数。
Format
Input
第一行包含一个整数 T(1≤T≤10)，表示测试用例的数量。
接下来 T行，每行包含一个整数 N。
Output
对于每个测试用例，输出一行，包含一个整数，表示区间 [1,N]内前缀素数的个数。
Samples
3
10
50
1000
4
8
27
Limitation
1s, 256MB for each test case.
SDNU_ACM_ICPC_2025秋季结训赛
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 12
- Start at
- 2025-12-28 9:00
- End at
- 2025-12-28 14:00
- Duration
- 5 hour(s)
- Host
-
sdnu_lijiaheng
- Partic.
- 37