最大质因子序列

题目描述

给定两个正整数 m, n（m ≤ n），对区间 [m, n] 中每个整数 i 求其最大质因子，并按 i 从小到大用逗号间隔输出。输入一行两个正整数 m, n，空格间隔；输出一行，即答案序列。

样例输入 5 10，样例输出 5,3,7,2,3,5（依次对应 5,6,7,8,9,10 的最大质因子）。

思路

对每个数从小到大试除因子并除尽：更小的因子已除尽，当前因子必为质数，省去单独判质数；循环结束时剩下的商就是最大质因子。因子只需试到 √N，2 之后只试奇数。

参考代码

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#!/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-07-05 22:10
# update_at: 2026-07-05 22:10

import sys


def largest_prime_factor(n: int) -> int:
    """返回 n 的最大质因子：从小到大除尽因子，剩下的商就是答案。"""
    factor = 2
    while factor * factor <= n:
        if n % factor == 0:
            n //= factor                    # 除尽这个因子，保证剩下的商不含更小因子
        else:
            factor += 1 if factor == 2 else 2   # 2 之后只试奇数
    return n                                # 循环结束时商本身就是最大质因子


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

    print(','.join(str(largest_prime_factor(i)) for i in range(m, n + 1)))


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/**
 * 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-05 23:10
 * update_at: 2026-10-05 23:10
 */
#include <cstdio>
using namespace std;

typedef long long ll;

ll m, n; // 区间左右端点，题目要求对 [m, n] 中每个数求最大质因子

// 返回 x 的最大质因子：从小到大除尽因子，最后剩下的商就是答案
ll largest_prime_factor(ll x) {
    ll factor = 2;
    while (factor * factor <= x) {
        if (x % factor == 0) {
            x /= factor; // 除尽这个因子，剩下的商不含更小的质因子
        } else {
            // 2 之后只试奇数，跳过偶数
            factor += (factor == 2 ? 1 : 2);
        }
    }
    return x; // 循环结束时商本身已是最大质因子（x 为质数时直接返回 x）
}

int main() {
    scanf("%lld %lld", &m, &n);

    // 按 i 从小到大输出每个数的最大质因子，用逗号间隔
    for (ll i = m; i <= n; i++) {
        if (i > m) {
            printf(",");
        }
        printf("%lld", largest_prime_factor(i));
    }
    printf("\n");

    return 0;
}

目录

题目描述

思路

参考代码