usaco-1.5.3 特殊的质数肋骨

题目描述

给定 N（1 ≤ N ≤ 8），求所有长度为 N 的“特殊质数”：从最高位开始切下任意前缀（含完整数本身）都必须是质数。按升序每行输出一个。

思路

一位数特殊质数只有 {2,3,5,7}。长度大于 1 时，末位只能是 {1,3,7,9}，否则会被 2 或 5 整除。逐位生长：对当前每个合法前缀，尝试接一位并试除判素，保留仍是质数的候选。由于按前缀升序、末位升序扩展，输出天然有序。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 03:18
# update_at: 2026-10-01 03:18

import sys

# 每一位只可能是这 4 个数字：偶数与 5 会让末位组成的数被 2 或 5 整除
TAIL_DIGITS = (1, 3, 7, 9)
# 首位从这 4 个里取：1 不是质数，2、3、5、7 都是一位质数
HEAD_DIGITS = (2, 3, 5, 7)


def is_prime(x: int) -> bool:
    """判断 x 是否为质数（试除到 sqrt(x)）。"""
    if x < 2:
        return False
    d = 2
    while d * d <= x:                # 只需试除到 sqrt(x)：合数必有一个不超过 sqrt(x) 的因子
        if x % d == 0:
            return False
        d += 1
    return True


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    # 逐位生长：prefix 是已经保证为特殊质数的前缀，往右再接一位再判定
    cur = [p for p in HEAD_DIGITS if is_prime(p)]   # 长度 1 的特殊质数
    for _ in range(n - 1):
        nxt: list[int] = []
        for prefix in cur:
            for d in TAIL_DIGITS:
                x = prefix * 10 + d
                if is_prime(x):                      # 新数仍是质数才留下，往后继续接
                    nxt.append(x)
        cur = nxt
        if not cur:                                  # 这一长度已经没有候选，再长更不可能有
            break

    sys.stdout.write('\n'.join(map(str, cur)) + ('\n' if cur else ''))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:41
 * update_at: 2026-10-06 09:41
 */
#include <iostream>
using namespace std;

typedef long long ll;

ll cur[20]; // 当前长度的特殊质数
ll nxt[40]; // 下一长度的候选
int cur_cnt, nxt_cnt;

// 试除判素：合数必有一个不超过 sqrt(x) 的因子
bool is_prime(ll x) {
    if (x < 2) return false;
    for (ll d = 2; d * d <= x; ++d)
        if (x % d == 0) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n)) return 0;

    // 长度 1 的特殊质数，1 不算质数
    cur[0] = 2; cur[1] = 3; cur[2] = 5; cur[3] = 7;
    cur_cnt = 4;

    // 逐位生长：由长度 k 的特殊质数，末位接 {1,3,7,9} 并判素，得到长度 k+1
    for (int k = 1; k < n; ++k) {
        nxt_cnt = 0;
        for (int i = 0; i < cur_cnt; ++i) {
            for (int d = 0; d < 4; ++d) {
                ll tail = (d == 0) ? 1 : (d == 1) ? 3 : (d == 2) ? 7 : 9;
                ll x = cur[i] * 10 + tail;
                if (is_prime(x)) nxt[nxt_cnt++] = x;
            }
        }
        // 把 nxt 复制回 cur
        cur_cnt = nxt_cnt;
        for (int i = 0; i < cur_cnt; ++i) cur[i] = nxt[i];
    }

    for (int i = 0; i < cur_cnt; ++i) cout << cur[i] << '\n';
    return 0;
}

usaco-1.5.3 特殊的质数肋骨

目录

题目描述

思路

参考代码